[백준] 11725번 : 트리의 부모 찾기

 

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

11725번: 트리의 부모 찾기

 

문제

 

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

 

입력

 

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

 

출력

 

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

 

 

풀이 방법

 

List<>[]와 배열을 합해서 트리를 작성한다.
양방향 그래프를 활용하여 노드를 연결한 뒤 루트노드부터 시작하여
연결된 노드를 따라가며 부모노드를 구한다.
부모 노드를 자식 노드보다 항상 먼저 방문하기 때문에
방문한 적이 없으면 현재 노드가 부모노드가 되고 연결되어 있는 노드가 자식 노드가 됨

작성 코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

package baekjoon.graphTraversal;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class BJ_11725 {       static int N;     static int parent[];     static boolean visited[];     static ArrayList<Integer> list[];       public static void main(String[] args) throws IOException {           BufferedReader br=new BufferedReader(new InputStreamReader(System.in));         N=Integer.parseInt(br.readLine());           parent=new int[N+1];         visited=new boolean[N+1];         list=new ArrayList[N+1];           for(int i=1;i<=N;i++){             list[i]=new ArrayList<>();         }           for(int i=1;i<N;i++){             StringTokenizer st=new StringTokenizer(br.readLine());             int u=Integer.parseInt(st.nextToken());             int v=Integer.parseInt(st.nextToken());             list[u].add(v);             list[v].add(u);         }           DFS(1);           for(int i=2;i<=N;i++){             System.out.println(parent[i]);         }     }       public static void DFS(int start){           visited[start]=true;           for(int i:list[start]){             if(visited[i]==false){                 parent[i]=start;                 DFS(i);             }         }       } }