백준/11725번 :: 트리의 부모찾기 (java 자바) - DFS, BFS 이용

 

문제

루트 없는 트리가 주어진다. 이 때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

---

예제입력1

7
1 6
6 3
3 5
4 1
2 4
4 7

 

예제출력1

4
6
1
3
1
4

 

---

예제입력2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

 

예제출력2

1
1
2
3
3
4
4
5
5
6
6

 

 

코드

방법1. BFS

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

public class Ex11725 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        // 인접 리스트
        ArrayList< ArrayList<Integer> > list = new ArrayList< ArrayList<Integer> >();
        int[] parents = new int[n+1];
        int i;
        for(i=0; i<=n+1; i++) {
            list.add(new ArrayList<Integer>());
        }
        
        // 연결 설정
        int a, b;
        for(i=1; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }
        
        // bfs
        int start = 1;
        bfs(start, list, parents, n);
        
        // 결과 출력
        printParents(parents);
    }

    private static void bfs(int start, ArrayList<ArrayList<Integer>> list, int[] parents, int n) {
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        parents[start] = 1;
        
        while(!queue.isEmpty()) {
            int parent = queue.poll();
            
            for(int item : list.get(parent)) {
                if(parents[item] == 0) {
                    parents[item] = parent;
                    queue.offer(item);
                }
                
            }// end for
        }
    }
    
    private static void printParents(int[] parents) {
        int i;
        for(i=2; i<parents.length; i++) System.out.println(parents[i]);
    }
}​

 

방법2. DFS

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

public class Ex11725_2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int i, j;
        
        // 연결 정보
        ArrayList<Integer>[] list = new ArrayList[n+1];
        // 초기화        
        for(i=1; i<=n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        
        // 연결
        for(i=0; i<n-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }
        
        // 결과 값(부모값)
        // 예: parents[i] = j (i의 부모 : j)
        int[] parents = new int[n+1];
        
        // dfs
        dfs(list, parents, n, 1, 0);
        
        // 결과 출력
        for(j=2;j<=n; j++) System.out.println(parents[j]);
    }

    private static void dfs(ArrayList<Integer>[] list, int[] parents, int n, int start, int parent) {
        // TODO Auto-generated method stub
        parents[start] = parent;
        for(int item : list[start]) {
            if(item != parent) dfs(list, parents, n, item, start);
        }
    }

}​

 

결국은 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 통해서 탐색을 하면 된다. 루트값이 1이므로 1부터 시작하면 된다. 

 

주의할 점이 있는데 n값이 100,000까지 들어갈 수 있기 때문에 인접행렬을 이용하면 "런타임 에러"가 발생한다. 그래서 인접행렬이 아닌 인접리스트를 이용해서 하는 것을 추천한다. (처음에 인접 행렬로 풀었다가 런타임 에러가 발생했다...)

 

결과

아래는 DFS로 풀었을때 채점 결과이고, 위에는 BFS로 풀었을때 채점 결과입니다.

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

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