AlgorithmBOJ

백준 부모의 트리찾기 11725

,

1. 트리의 부모찾기 문제

1.1. 컴퓨팅적 사고

    1. 인접리스트로 해당되는 그래프를 연결시킨다.
    1. dfs로 해당되는 모든 부모의 값을 배열 갱신시킨다.(단 루트노드는 1번 부터 시작된다.) 시작점
  • 예) parent[y] = x
    1. 최종적으로 parent에는 각 노드 2번부터 n번까지 부모의 값이 담겨져 있다.

1.2. 소스코드

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
public class boj_11725 {
    static List<List<Integer>> graphList;
    static boolean[] isChecked;
    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;
        graphList = new ArrayList<>();
        isChecked = new boolean[n+1];
        parent = new int[n+1];
        for(int i=0; i<=n; i++){
            graphList.add(new ArrayList<>());
        }

        for(int i=0; i<n-1; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graphList.get(x).add(y);
            graphList.get(y).add(x);
        }
        // root is 1
        findParent(1);
        for(int i=2; i<parent.length; i++){
            System.out.print(parent[i] + " ");
        }

    }

    private static void findParent(int x) {
        isChecked[x] = true;
        for(int i=0; i<graphList.get(x).size(); i++){
            int y = graphList.get(x).get(i);
            if(!isChecked[y]){
                parent[y] = x;
                findParent(y);
            }
        }
    }
}
Share