백준 1325번 자바

1. 문제

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

2. 접근방식

dfs, bfs 둘 다 접근 가능한 방법이다. 다만 처음에 방문 배열을 사용하지 않고 접근해서 시간초과가 났다.

방문배열을 사용해야 하는 이유는 다음과 같다.

1 4 

3 2

3 1

4 3

1 - 4 - 3 이 순환을 하며 계속 다음 노드를 탐색하기 때문이다.

사실 이 부분이 시간초과를 뜨게한 주 원인인지는 확실하지 않다. 이런 식으로 순환을 하면 스택오버플로우 오류가 뜨는게 타당한 것 같은데 해당 오류가 뜨지 않아서 다른 이유 일수도 있다고 생각한다.

어쨌든 dfs,bfs 둘 다 사용가능하고 방문배열을 유의해서 사용하면 된다.

3. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int N,M;
	static List<Integer>[] computers;
	static int max;
	static int[] result;
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		computers = new ArrayList[N+1];
		result = new int[N+1];
		visited = new boolean[N+1];
		for (int i=1; i<=N; i++) {
			computers[i] = new ArrayList<Integer>();
		}
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			computers[start].add(end);
		}
		for (int i=1; i<=N; i++) {
			visited = new boolean[N+1];
			dfs(i);
		}
		for (int i=1; i<=N; i++) {
			if (max < result[i]) {
				max = result[i];
			}
		}
		StringBuffer sb = new StringBuffer();
		for (int i=1; i<=N; i++) {
			if (max == result[i]) {
				sb.append(i+" ");
			}
		}
		System.out.println(sb.toString());
	}
	
	public static void dfs(int idx) {
		visited[idx] = true;
		for (int computer : computers[idx]) {
			if (!visited[computer]) {
				result[computer]++;
				dfs(computer);
			}
		}
	}
}

4. 정리

나를 포함한 대부분이 dfs 또는 bfs의 전형적인 방식을 사용해서 문제를 해결했다. 대개 7500ms ~ 11000ms로 통과한듯 하다. 하지만 아래 두 링크의 결과를 보면 2500ms ~ 3500ms로 문제해결을 한다. 사실 잠깐 들여다보긴 했지만 정확하게 코드를 이해하지 못했다. 추후 시간이 되면 해당 코드들을 분석해서 어떻게 시간을 3분의1로 단축했는지 파악해보자.

https://www.acmicpc.net/source/49027563

https://www.acmicpc.net/source/56140559