[백준] 11725번 트리의 부모찾기 문제 풀어보기 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/11725

2) 문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

3) 입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

4) 출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

문제의 자세한 사항은 위의 백준 링크에 들어가서 살펴보자.

2. 풀이

이 문제는 트리의 부모를 찾는 문제인데 원래 트리의 일반적인 형식인 [현재 노드, 왼쪽 자식노드, 오른쪽 자식노드] 처럼 입력이 주어지지 않고 연결되어 있는 두 노드를 입력으로 주는 형식의 문제이다.

따라서 이는 그래프의 연결리스트를 사용하면 된다. 또한 그래프를 순회해야 하기 때문에 BFS와 DFS 중에서 한 가지를 선택해서 사용하면 된다. 나는 BFS의 방법을 사용하여 트리를 순회하는 것을 택했다.

그래서 사실상 이 문제는 그래프 문제 BFS라고 봐도 무방하다.

여기서 다른 점은 부모를 저장할 배열을 하나 만들어줘야 한다는 것과 BFS를 순열을 돌면서 부모를 저장해주어야 한다는 점이다. 루트부터 시작함으로 부모-자식 관계는 명확하기 때문에 이것이 가능하다.

BFS관련 코드는 다음과 같다.

Queue<Integer> q=new LinkedList<>();
        q.add(1);
        check[1]=true;
        while(!q.isEmpty()){
            int x=q.remove();
            for(int y: a[x]){
                if (!check[y]){
                    q.add(y);
                    parent[y]=x;
                    check[y]=true;
                }
            }
        }

예전 그래프에서 풀던 것과 같은 형태인데 parent[y]=x; 부분만 추가되었다는 것을 알 수 있다.

만약 루트가 문제에서 1이라고 주어지지 않았다면

https://www.programmingstory.com/2024/03/2250-in-order.html

전의 포스팅처럼 루트를 찾아주어야 한다.

하지만 이 문제는 루트가 1이라고 명시적으로 주어졌기 때문에 편하게 구할 수 있다.

3. 코드

전체 소스코드를 살펴보면, 아래와 같다.

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        ArrayList<Integer> a[]=(ArrayList<Integer>[])new ArrayList[n+1];
        boolean check[]=new boolean[n+1];
        int parent[]=new int[n+1];
        for(int i=1; i<=n; i++){
            a[i]=new ArrayList<Integer>();
        }
        for(int i=0; i<n-1; i++){
            int from=sc.nextInt();
            int to=sc.nextInt();
            a[from].add(to);
            a[to].add(from);
        }
        Queue<Integer> q=new LinkedList<>();
        q.add(1);
        check[1]=true;
        while(!q.isEmpty()){
            int x=q.remove();
            for(int y: a[x]){
                if (!check[y]){
                    q.add(y);
                    parent[y]=x;
                    check[y]=true;
                }
            }
        }
        for(int i=2; i<=n; i++){
            System.out.println(parent[i]);
        }
    }
}

이 문제는 겉으로 보기에는 트리 문제이지만 사실상 그래프 문제에 더 가까운 형태의 문제이다.