[알고리즘 PS] 백준 11725번 트리의 부모 찾기 자바 문제풀이

문제

해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

11725번: 트리의 부모 찾기

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 주어진 입력의 순서대로 자식과 부모의 관계 라고 생각해서 조금 오래 걸렸던 문제이다.

 

그래서 나는 Tree 의 특성과 개념을 이용해서 Node 를 만들어 풀려고 했지만, 계속 안되는 것 같아서 풀이를 보니 DFS 를 이용해서 푸는게 정석인 방법 같았다.

 

해결법

 

우선 트리의 연결 관계에 대해서 알지 못하니 양방향 그래프로 만들어주고, 현재 방문한 노드에서 그 다음 노드는 무조건 자식으로 볼 수 있다.

 

이 특성을 이용해서 dfs 를 돌리면 된다.

 

정답 코드

public class Main {

    private static List<List<Integer>> tree = new ArrayList<>();
    private static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        parent = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }

        while(n-- > 1) {
            String[] s = br.readLine().split(" ");
            int from = Integer.parseInt(s[0]);
            int to = Integer.parseInt(s[1]);

            tree.get(from).add(to); // 왜 단방향이 아닐까?
            tree.get(to).add(from);
        }

        dfs(1);

        for (int i = 2; i < parent.length; i++) {
            bw.write(parent[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void dfs(int start) {
        for(int value : tree.get(start)) {
            if(parent[value] == 0) {
                parent[value] = start;
                dfs(value);
            }
        }
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.