BOJ 11725 트리의 부모 찾기(Java)

문제 탐색하기

트리가 주어지며, 이 트리의 루트는 1으로 가정한다. 이때 2번째 노드부터, 각 노드의 부모 번호를 순서대로 출력한다.

코드 설계하기

입출력 예시 1에 해당하는 경우를 실제 트리와 같은 모습으로 확인하면 다음과 같이 나타난다.

구현 방법

• 자료구조 선택
  • List<List<Integer>> nodes
    • 각 노드와 연결된 인접 리스트를 저장하는 ArrayList
    • 노드 간의 연결 정보를 저장하여, DFS 탐색 시 인접한 노드를 쉽게 접근할 수 있다.
  • int[] parent 각 노드의 부모 노드를 기록한다.
  • boolean[] visited
    • 노드의 방문 여부를 기록한다.
• 그래프 구성
  • 문제에서 주어진 간선 정보(양방향)를 입력받는다.
  • nodes.get(a).add(b)와 nodes.get(b).add(a)를 수행하여 양방향 그래프를 구성한다.
• DFS 탐색 수행
  • 루트 노드인 1번 노드부터 DFS 탐색을 시작한다.
  • 재귀 함수 DFS(cur)
    • 현재 노드 cur를 방문 처리 (visited[cur] = true)
    • cur와 인접한 모든 노드 (i)에 대해, 아직 방문하지 않은 경우 DFS(i)를 재귀 호출한다.
    • 재귀 호출 후, (i)의 부모는 현재 노드 cur로 설정한다.
      • (parent[i] = cur)
• 부모 배열 출력
  • 루트 노드(1번)는 출력하지 않고, 2번부터 (N)번 노드의 부모 노드를 순차적으로 출력한다.

시간 복잡도

• 노드 개수: (N)

• 간선 개수: (N - 1) (트리의 특성)

• DFS 탐색은 모든 노드와 간선을 한 번씩 방문한다.
• 각 노드는 한 번씩 방문되며, 각 간선은 양쪽에서 한 번씩 확인되지만, 이미 방문한 노드는 다시 탐색되지 않으므로 전체적으로 (O(N))의 시간 복잡도를 가진다.
• 최악의 경우 시간 복잡도는 (O(N + N - 1) = O(N), 2 ≤ N ≤ 100,000 이므로, 시간 내에 연산이 가능하다.

정답 코드 (Java)

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 b11725 {  
    private static int N;  
    private static List<List<Integer>> nodes = new ArrayList<>();  
    private static int[] parent;  
    private 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());  
        parent = new int[N + 1];  
        visited = new boolean[N + 1];  
  
        for (int i = 0; i <= N; i++) {  
            nodes.add(new ArrayList<>());  
        }  
  
        for (int i = 0; i < N - 1; i++) {  
            st = new StringTokenizer(br.readLine());  
            int a = Integer.parseInt(st.nextToken());  
            int b = Integer.parseInt(st.nextToken());  
            nodes.get(a).add(b);  
            nodes.get(b).add(a);  
        }  
  
        // 1번 노드를 루트 노드(시작 노드)로 해 탐색한다.  
        DFS(1);  
  
        for (int i = 2; i < parent.length; i++) {  
            System.out.println(parent[i]);  
        }  
  
    }  
  
    private static void DFS(int cur) {  
        visited[cur] = true;  
  
        // 현재 노드와 연결된 노드들 방문하게 한다.  
        for (int i : nodes.get(cur)) {  
            if (!visited[i]) {  
                DFS(i);  
                // 방문되는 노드의 부모 노드는 현재 노드이다.  
                parent[i] = cur;  
            }  
        }  
    }  
}