[Java] 트리의 부모 찾기 (Lv. Sliver2)

트리의 부모 찾기 (Lv. Sliver2)

---

1. 문제
2. 풀이

---

1. 문제

https://www.acmicpc.net/problem/11725
 

2. 풀이

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

class Main {
    static int N;
    static ArrayList<Integer>[] graph;
    static int[] parent;
    static boolean[] visited;
    
    public static void find_parent(int node) {
        visited[node] = true;
        
        for (int i : graph[node]) {
            if (!visited[i]) {
                parent[i] = node;
                find_parent(i);
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        graph = new ArrayList[N + 1];
        parent = new int[N + 1];
        visited = new boolean[N + 1];
        
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < N - 1; i++) {
            StringTokenizer 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);
        }
        
        find_parent(1);
        
        for (int i = 2; i <= N; i++) {
            System.out.println(parent[i]);
        }
    }
}

 
트리의 부모가 주어지지 않은 문제였습니다. ArrayList를 활용하여 graph[1] = [2, 3]; graph[2] = [1, 4, 5]; graph[3] = [1]; graph[4] = [2]; graph[5] = [2]; 과 같은 형태로 저장합니다.
 

for (int next : graph[node]) {
    if (!visited[next]) {
        parent[next] = node;
        find_parent(next);
    }
}

 
graph[node]는 현재 노드 node와 연결된 모든 노드(next)를 나타냅니다. 처음에 node 값으로 1이 들어왔을 때 next는 2와 3이 될 수 있습니다. next를 방문하지 않았다면 현재의 노드값을 부모값으로 할당하고 next를 부모로 가지는 자식을 찾기 위해 재귀적으로 호출합니다.

---

문제가 있으면 댓글 남겨주세요 !
피드백은 언제나 환영입니다 <3