[백준] 11725번 - 트리의 부모 찾기 Python, Java

문제

---

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

입력

---

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

출력

---

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

예제 입력 1

---

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

---

4
6
1
3
1
4

나머지 예제 입출력은 생략한다.

풀이

---

Python

from collections import deque
import sys
input = sys.stdin.readline

n = int(input().rstrip())
g = [[] for _ in range(n+1)]
p = [0 for _ in range(n+1)]

for _ in range(n-1):
    a,b = map(int , input().rstrip().split())
    g[a].append(b)
    g[b].append(a)

def bfs():
    q = deque()
    q.append(1)

    while q:
        node = q.popleft()
        for i in g[node]:
            if p[i] == 0:
                p[i] = node
                q.append(i)

bfs()

for i in range(2,n+1):
    print(p[i])

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        Queue<Integer> q = new LinkedList<>();
        ArrayList<Integer>[] list = new ArrayList[n+1];
        int[] p = new int[n+1];
        for(int i = 1; i<=n;i++) {
            list[i] = new ArrayList<Integer>();
        }
        for(int i = 0; i <n-1;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        q.offer(1);
        boolean[] v = new boolean[n+1];
        while(!q.isEmpty()) {
            int node = q.poll();
            for(int x : list[node]) {
                if(p[x] == 0) {
                    p[x] = node;
                    q.offer(x);
                }
            }
        }
        for(int i = 2; i<=n; i++) {
            System.out.println(p[i]);
        }
    }
}

정리

---

• bfs나 dfs를 이용해 노드를 순회하며 p(자신의 부모에 대한 배열)을 값을 채워가면된다.