백준 No.11725 트리의 부모 찾기- JAVA

문제

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

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

 

 

풀이

주어진 노드들을 연결해보면 원을 막 뒤엉키게 되는데 루트를 1로 보면 이진트리로 볼 수 있다. 그렇게 보면 결국 주어진 값에서 루트 노드 1에 연결된 그래프는 4와 6이다. 이 두 값에 노드는 부모는 1인 걸 알 수 있다. 이 말을 보자마자 bfs로 풀면 금방 풀 수 있을 거 같았는데 dfs 로 한 번 도전해봤다. parent ,visited , graph 배열을 통해 값들을 받는데 핵심은

static void dfs(int index){
	
    visited[index] = true; //1이 들어오면 1을 방문처리하고 그의 자식들을 탐색한다.
    
    for(int temp : graph.get(index)){	//1의 자식 4, 6을 탐색
    	if(!visited[temp]){	  //해당 노드들을 방문하지 않았을 경우
        	parent[temp] = index;	//parent[4] = 1 -> 노드 4의 부모는 1이다.
            dfs(temp); //재귀
        }
    }

}

 

답

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

public class Main {

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean visited[];
    static int parent[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;

        visited = new boolean[N+1];
        parent = new int[N+1];

        for (int i = 0; i < N+1 ; i++) {
            graph.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());

            graph.get(a).add(b);    //양방향
            graph.get(b).add(a);
        }

        dfs(1);

        for (int i = 2; i < N+1 ; i++) {
            System.out.println(parent[i]);
        }
    }

    static void dfs(int index){
        visited[index] = true;

        for(int temp : graph.get(index)){
            if(!visited[temp]){
                parent[temp] = index;
                dfs(temp);
            }
        }
    }
}