[백준] 11725번 트리의 부모 찾기 (JAVA)

10000JI·2024년 7월 9일
0

코딩 테스트

목록 보기
34/39
post-thumbnail

문제사항

실버 2단계 문제였다.

앞서 풀었던 [백준] 1068번 트리 (JAVA)와 비슷한 유형이며, 난이도는 더 쉬운 문제이다.

1068번 문제를 풀 때 단뱡향 그래프를 사용하는 방법과 양방향 그래프를 사용하는 방법 두 가지 방법으로 나눠 풀었었다.

트리의 부모 찾기 문제도 부모를 찾기 위해서는 양방향 그래프로 접근해야 한다.

예제 입력 1을 그래프로 표현해보면

위와 같은 트리로 나타낼 수 있고, 출력은 2의 부모 4, 3의 부모 6, 4의 부모 1, 5의 부모 3, 6의 부모 1, 7의 부모 4 이므로 "4 6 1 3 1 4" 가 출력된다.

알고리즘 분류

트리, DFS

코드

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph;
    static int[] parent;
    static boolean[] visited;
    static int N, answer;

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

        for (int i = 0; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N-1; i++) { 
		//트리에서 간선의 수는 항상 노드의 수보다 1 적다
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        DFS(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i < parent.length; i++) {
            sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
    }


    static void DFS(int v) {
        visited[v] = true;
        for (int current : graph[v]) {
            if (!visited[current]) {
                parent[current] = v;
                DFS(current);
            }
        }
    }
}
profile
Velog에 기록 중

0개의 댓글