[Algorithm] Baekjoon/백준 11725 트리의 부모 찾기 Java

문제

문제 설명

입/출력

입력

출력

예제

풀이

1. 문제의 예제를 그림으로 그려서 접근해본다.

1. 탐색을 진행하며 정점의 부모를 찾기보다, 해당 정점이 누구의 부모인지 찾자.

2. 재귀적으로 DFS를 호출할때, 연결되어 있는 다음 정점의 번호와 현재 노드의 번호를 같이 넘겨 다음 노드와 연결되어 있는 정점 중 현재 노드를 제외한 값이 부모가 된다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 문제5 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int N;
    static ArrayList<Integer>[] graph;
    static int[] parents;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        parents = new int[N + 1]; // 부모를 저장할 배열, 각 인덱스의 값이 부모다.
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
        for (int i = 1; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
            graph[x].add(y);
            graph[y].add(x);
        }
        solution();
    }
    static void solution(){
        DFS(1,-1); //<- 1의 루트는 없으니 아무 숫자 설정
				// 0과 1은 비어있으니 두 번재 인덱스부터 출력
        for(int i = 2 ; i<parents.length;i++){
            sb.append(parents[i]).append('\n');
        }
            System.out.println(sb.toString());

    }
		// x = 다음 노드, parent = 부모 노드
    static void DFS(int x, int parent){
        for(int y : graph[x]){ // x와 연결된 간선을 확인
            if(y == parent) continue; //부모 노드는 제외한다. == 다음 정점의 간선이 기존의
            parents[y] = x;           //기존의 정점을 공유 한다면 같은 부모 노드 이기 때문에 제외
            DFS(y,x); //y 다음 정점 번호/ x 현재 정점 번호
        }
    }
}