[백준(Python/Java)] 11725_트리의 부모찾기(DFS, BFS)

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

11725번: 트리의 부모 찾기

트리의 연결 정보가 주어졌을 때, 각 노드의 부모 노드가 몇 번 노드인지를 묻는 문제입니다.

 

문제 조건에서 루트 노드가 항상 1번이라는 조건이 있으므로 1번 노드부터 DFS나 BFS 탐색을 시작합니다. 현재 노드를 A라고 하고 그 다음에 탐색을 할 노드를 B라고 한다면, B노드의 부모는 A가 되므로 한 번의 DFS 혹은 BFS 수행으로 모든 노드의 부모 노드를 정할 수 있습니다.

 

저 같은 경우에는 BFS를 이용해서 문제를 해결했습니다.

 

 

[풀이 - 파이썬]

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

# 루트 노드부터 너비 우선 탐색
def findParent():
    visited = [False] * (n+1)
    visited[1] = True
    q = deque()
    q.append(1)
    while q:
        parent = q.popleft()
        for child in tree[parent]:
            if not visited[child]:
                parentNumber[child] = parent
                visited[child] = True
                q.append(child)


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

# 각 노드의 부모 번호를 저장하는 리스트
parentNumber = [-1] * (n+1)

# BFS를 통해 각 노드의 부모 노드 찾기
findParent()

# 결과 출력
for i in range(2, n+1):
    print(parentNumber[i])

 

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class B_11725 {
    static int n;
    static int[] parentNum;
    static boolean[] visited;
    static List<Integer>[] tree;


    public static void findParent(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        visited[1] = true;

        while(!q.isEmpty()){
            int curr = q.poll();
            for(Integer child : tree[curr]){
                if(!visited[child]){
                    visited[child] = true;
                    parentNum[child] = curr;
                    q.offer(child);
                }
            }
        }
    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        // ArrayList 초기화
        tree = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++){
            tree[i] = new ArrayList<>();
        }

        // 연결 정보 입력받기
        for(int i = 0; i < n-1; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree[a].add(b);
            tree[b].add(a);
        }

        parentNum = new int[n+1];
        visited = new boolean[n+1];
        findParent();

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i < n+1; i++) {
            sb.append(parentNum[i] + "\n");
        }
        System.out.println(sb);



    }
}