[백준/BOJ/JAVA] 11725 트리의 부모 찾기

 

 

입력된 트리의 루트를 1이라고 가정한다.

각 노드의 부모를 구하는 문제!!

 

노드들의 연결 정보를 list에 저장시켜 놓고 재귀함수를 돌며 부모노드를 찾는다.즉, 부모노드 정보를 저장할 parents 변수가 하나 더 필요함

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class BOJ_11725 {
    static int N;
    static int[] parents;
    static ArrayList<Integer>[] list;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N+1];
        parents = new int[N+1];
        
        for(int i=1; i<=N; i++){
            list[i] = new ArrayList<Integer>();
        }
 
        // list에 연결 정보 저장
        for(int i=1; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int temp1 = Integer.parseInt(st.nextToken());
            int temp2 = Integer.parseInt(st.nextToken());
            list[temp1].add(temp2);
            list[temp2].add(temp1);
        }
        
        dfs(1);
        
        for(int i=2; i<=N; i++){
            bw.write(parents[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
 
    private static void dfs(int now) {
        for(int child : list[now]){
            //이미 부모가 있다면
            if(parents[child] != 0) continue;
 
            parents[child] = now;
            dfs(child);
        }
    }
}

 

재귀를 도는 방법 말고, 큐를 사용하는 방법도 있다. (bfs)

BOJ - 트리의 부모 찾기 (11725 번) - Tree, 재귀, BFS