[백준] 16940번 : BFS 스페셜 저지 - JAVA [자바]

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

---

bfs 알고리즘 문제이다.

그림을 보고 이해해 보자.

이러한 그래프가 있다고 해보자.
문제에서 1부터 방문한다고 하였으니 1은 고정이다.

1. 먼저 1을 방문한다.
2. 1의 자식 노드인 2와 3 중 2를 먼저 방문하고 3을 방문한다.
3. 그 다음 2의 자식 노드인 4를 방문한다.
4. 그 이후 3의 자식 노드인 5를 방문한다.

위의 방법대로 방문했을 때, 정답은 1 2 3 4 5 이다.

여기서 2번을 수정해보자.

1. 먼저 1을 방문한다.
2. 1의 자식 노드 중 3을 먼저 방문하고 2를 방문한다.
3. 그 이후 3의 자식 노드인 5를 방문한다.
4. 그 다음 2의 자식 노드인 4를 방문한다.

수정된 방법대로 하면, 정답은 1 3 2 5 4 이다.

즉, bfs 알고리즘의 방문 순서를 보면 부모 노드에 따라 방문 순서가 바뀌는 것을 알 수 있다.

이제 푸는 코드를 보자.

private static boolean checkBFS() {
	// 시작을 1로 초기화하고 방문처리를 해준다.
	int start = 1;
    visited[start] = true;
    // 큐에 1을 삽입한다.
    queue.add(start);
    // 1의 자식 index는 0 다음인 1부터 시작이므로 (입력으로 받은 방문순서 배열에서의 index)
    childIndex = 1;

	while (!queue.isEmpty()) {
		start = queue.poll();
        // 각 부모 노드의 자식 카운트 초기화
        int childCount = 0;
        // 부모 노드와 연결된 간선을 보면서 자식을 찾는다.
        for (int to : edgeList.get(start)) {
        	// 방문하지 않았으면 자식
        	if (!visited[to]) {
            	// 자식을 방문처리 해준다. (자식인지 아닌지 구분하기 위해)
            	visited[to] = true;
                // 자식의 수를 센다.
                childCount++;
			}
		}

		// 입력으로 받은 방문 순서 배열에서
        // 현재 부모의 자식 노드라고 추정되는 index 부터 자식의 수만큼 탐색한다.
		for (int i = childIndex; i < childIndex + childCount; i++) {
        	// 방문 처리가 안된 노드는 자식 노드가 아니므로 오답이다.
            if (!visited[inputAnswer[i]]) {
            	return false;
			} 
            // 자식 노드들은 방문 처리를 했으므로
            // bfs 알고리즘을 더 진행하기 위해 큐에 삽입 
            else queue.add(inputAnswer[i]);
		}
        // 다음 계층으로 넘어갔을 때의 검증을 위해
        childIndex += childCount;
	}
    return true;
}

추가로 처음 입력에서 방문 순서가 1부터 되어 있지 않으면 문제의 조건이 맞지 않으므로 바로 0을 출력한다.

---

public class bj16940 {

    public static int N;
    public static boolean[] visited;
    public static int[] inputAnswer;
    public static int index;
    public static Queue<Integer> queue = new LinkedList<>();
    public static ArrayList<ArrayList<Integer>> edgeList;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        visited = new boolean[N + 1];
        inputAnswer = new int[N];

        edgeList = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            edgeList.add(new ArrayList<>());
        }

        for (int i = 0; i < N - 1; i++) {
            String line1 = br.readLine();
            String[] split1 = line1.split(" ");
            int from = Integer.parseInt(split1[0]);
            int to = Integer.parseInt(split1[1]);
            edgeList.get(from).add(to);
            edgeList.get(to).add(from);
        }

        String line = br.readLine();
        String[] split = line.split(" ");
        for (int i = 0; i < N; i++) {
            inputAnswer[i] = Integer.parseInt(split[i]);
        }

        boolean checkBFS = checkBFS();

        if (inputAnswer[0] != 1) checkBFS = false;

        if (checkBFS) sb.append(1);
        else sb.append(0);

        bw.write(sb + "");

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean checkBFS() {
        int start = 1;
        visited[start] = true;
        queue.add(start);
        index = 1;

        while (!queue.isEmpty()) {
            start = queue.poll();
            int childCount = 0;
            for (int to : edgeList.get(start)) {
                if (!visited[to]) {
                    visited[to] = true;
                    childCount++;
                }
            }

            for (int i = index; i < index + childCount; i++) {
                // 자식 노드들은 방문 처리를 했으므로
                if (!visited[inputAnswer[i]]) {
                    return false;
                } else queue.add(inputAnswer[i]);
            }
            index += childCount;
        }
        return true;
    }
}