백준 11725 : 트리의 부모 찾기 [JAVA]

[문제 링크]

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

[난이도]

- Silver 2

 

[알고리즘]

- BFS

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        List<List<Integer>> tree = new ArrayList<>(); // 트리 선언
        for (int i = 0; i < n + 1; i++) {
            tree.add(new ArrayList<>()); // 자식노드가 없는 정점 n+1개 생성
        }

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            tree.get(u).add(v);
            tree.get(v).add(u);
        }

        int[] parent = new int[n + 1]; // 각 노드의 부모를 저장
        boolean[] visited = new boolean[n + 1]; // 노드 방문 여부를 체크
        Queue<Integer> queue = new LinkedList<>(); // 큐를 사용해 bfs로직 수행
        queue.add(1); // 루트노드는 1
        visited[1] = true; // 루트노드는 방문함

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에 담긴 노드를 선택
            for (int neighbor : tree.get(node)) { // 선택한 노드와 연결된 모든 노드를 탐색
                if (!visited[neighbor]) { // 선택한 노드와 연결된 노드가 방문하지 않았다면 진행
                    visited[neighbor] = true; // 방문한것으로 체크
                    parent[neighbor] = node; // 선택한 노드와 연결된 노드는 선택한 노드의 자식임
                    queue.add(neighbor); // 큐에 추가
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) { // 2번노드부터 부모노드를 출력
            sb.append(parent[i]).append('\n');
        }

        System.out.print(sb);
    }
}

[풀이]

트리구조, 노드 탐색문제는 많이 나오기 때문에 트리구조를 선언하는법, 자식노드를 추가하는법 등을 알아두어야 한다고 생각한다. 

 

2중 list를 활용해 트리구조를 선언 한다. 무엇이 부모, 자식 관계가 없는 단순 쌍방으로 연결된 구조이다.

List<List<Integer>> tree = new ArrayList<>(); // 트리 선언

 

 

for문을 활용해 정점를 생성한다. list구조이기 때문에 가변적으로 연결된 정점을 추가할 수 있다.

        for (int i = 0; i < n + 1; i++) {
            tree.add(new ArrayList<>()); // 정점 n+1개 생성
        }

 

 

양방향으로 연결된 간선이므로 각 정점에 서로 추가해준다.

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            tree.get(u).add(v);
            tree.get(v).add(u);
        }

 

 

parent[n] 는 n정점의 부모노드의 정보를 담은 배열. ex) parent[2] = 4, 2번 정점의 부모노드는 4임.

이미 방문한 노드는 재방문하면 안되므로 visited배열로 체크해준다.

루트노드는 1로 문제에서 정해주었다. 루트노드부터 bfs를 시작하기위해 큐에 담아준다.

        int[] parent = new int[n + 1]; // 각 노드의 부모를 저장
        boolean[] visited = new boolean[n + 1]; // 노드 방문 여부를 체크
        Queue<Integer> queue = new LinkedList<>(); // 큐를 사용해 bfs로직 수행
        queue.add(1); // 루트노드는 1
        visited[1] = true; // 루트노드는 방문함

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에 담긴 노드를 선택
            for (int neighbor : tree.get(node)) { // 선택한 노드와 연결된 모든 노드를 탐색
                if (!visited[neighbor]) { // 선택한 노드와 연결된 노드가 방문하지 않았다면 진행
                    visited[neighbor] = true; // 방문한것으로 체크
                    parent[neighbor] = node; // 선택한 노드와 연결된 노드는 선택한 노드의 자식임
                    queue.add(neighbor); // 큐에 추가
                }
            }
        }