백준 Q11725 - 트리의 부모 찾기

처음 코드

private static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    int findNodeNumber = 2;
    while (findNodeNumber < N + 1) {
        queue.add(start);
        int current = queue.poll();
        for (Integer node : link[current]) {
            if (node == findNodeNumber) {
                result[findNodeNumber - 1] = current;
                findNodeNumber++;
            } else {
                queue.add(node);
       		}
        }	
    }
}

그래프를 탐색할때 흔히 쓰는 visited 배열을 사용하지 않고, nodeNumber를 찾는 방식으로 구현했었다. 입출력은 모두 잘 되지만 테스트 제출시 메모리 초과 에러가 발생하였다.
매 번 새로운 노드를 찾기 시작할때 마다 start node 인 1 부터 반복을 하여 메모리 과부화로 해당 에러가 발생한 것 같다.

수정한 최종 코드

private static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
        int current = queue.poll();
        for (Integer node : link[current]) {
            if (!visited[node]) {
                visited[node] = true;
                parent[node] = current;
                queue.add(node);
            }
        }
    }
}

일반적인 bfs 구현처럼 visited 배열로 방문여부를 체크하며 탐색을 진행하였고, 이때 큐에서 poll 한 루트노드의 자식노드들을 탐색과 동시에 parent[ ] 인덱스로 설정하여 해당 자식의 부모노드 값을 지정했다.

문제를 풀다가 뜬겁새로 들었던 생각인데 트리는 순환을 갖지 않는 그래프 인데 왜 굳이 visited[ ] 배열을 사용해야 할까 싶었다..

그래프를 구현할 때 (1,6), (6,3) 간선에 대해

link[1].add(6)
link[6].add(1)

link[6].add(3)
link[3].add(6)

양쪽 리스트에 추가를 해줬으므로 방문여부를 체크하지 않으면,
while(!queue.isEmpty()) 조건에 항상 참이므로... 무한루프에 빠지겠지...

뭐 이런 당연한걸 고민했는지 알고리즘 공부좀 다시 열심히 해야겠다