[백준] 11725 트리의 부모 찾기 - Graph Theory / Java

• 문제 링크

11725번: 트리의 부모 찾기

 

• 풀이 과정

각 노드의 부모 노드를 저장할 parent, 방문 여부를 확인할 visit 배열을 생성하고,

인접 리스트를 활용하여 트리의 무향 그래프 정보를 입력받아 저장하며 각각의 크기는 n(노드의 개수) + 1 로 지정한다.

 

문제에 주어진 조건에 따라 루트 노트 1에서 부터 BFS 탐색을 수행한다.

인접 리스트에 저장된 각각의 노드와 연결된 노드를 탐색하여 parent 배열에 현재 노드의 부모 노드를 저장한다.

 

이 후 루트 노드를 제외한 나머지 노드의 부모 노드들을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static List<Integer>[] tree;
    static int[] parent;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n + 1];
        parent = new int[n + 1];
        visit = new boolean[n + 1];

        for (int i = 0; i <= n; i++)
            tree[i] = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());

            tree[src].add(dest);
            tree[dest].add(src);
        }

        bfs();

        for (int i = 2; i <= n; i++)
            bw.write(parent[i] + "\n");

        bw.flush();
    }

    private static void bfs() {
        Queue<Integer> q = new LinkedList<>();

        q.offer(1);
        visit[1] = true;

        while (!q.isEmpty()) {
            int src = q.poll();

            for (int dest : tree[src]) {
                if (!visit[dest]) {
                    visit[dest] = true;
                    parent[dest] = src;
                    q.offer(dest);
                }
            }
        }
    }

}