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

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

728x90

문제

해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다.

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

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

문제 접근

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

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

해결법

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

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

정답 코드

public class Main { private static List> 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] + "

"); } 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 에서 확인 가능합니다.

728x90

from http://wonit.tistory.com/563 by ccl(S) rewrite - 2021-10-27 20:59:49