[백준 / 실버2] 11725 트리의 부모 찾기 (Java)

문제 보기

사용한 것

• 트리의 root 부터 시작하여 순회하기 위한 DFS

풀이 방법

• map에 두 정점 연결 정보를 저장한다.
  • 입력 값의 순서는 "부모 자식"이 아니기 때문에 map에 양방향으로 넣어준다.
  • 트리에 여러 자식이 있을 수 있고, 부모까지 value인 리스트에 들어갈 수 있다.
• root인 1을 시작으로 DFS 한다.
  • 리스트에 자식만 있는게 아니기 때문에 set으로 방문 여부 확인한다.
  • 부모 배열을 채워주고 set에 추가해 방문 처리 후 재귀 호출한다.

코드

public class Main {

    private static int n;
    private static int[] parents;
    private static Map<Integer, List<Integer>> map;
    private static Set<Integer> set;

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line;
        n = Integer.parseInt(br.readLine());
        parents = new int[n + 1];
        map = new HashMap<>();
        set = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            map.put(i, new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            line = br.readLine().split(" ");
            int v1 = Integer.parseInt(line[0]);
            int v2 = Integer.parseInt(line[1]);
            map.get(v1).add(v2);
            map.get(v2).add(v1);
        }

        dfs(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb.append(parents[i]).append(lineSeparator());
        }
        System.out.println(sb);
    }

    private static void dfs(int v) {
        List<Integer> list = map.get(v);
        for (int i : list) {
            if (!set.contains(i)) {
                parents[i] = v;
                set.add(i);
                dfs(i);
            }
        }
    }
}