[BOJ] 11725. 트리의 부모 찾기 (python / java)

백준 11725. 트리의 부모 찾기 (파이썬 / 자바)

11725번: 트리의 부모 찾기

파이썬

양방향 모두 저장한 후 접근

아직 탐색하지 않은 값이 있다면 그 인덱스의 자식에 해당

import sys
sys.setrecursionlimit(10**6)	# 안하면 recursionError
input = sys.stdin.readline

def search(v):
    visited[v] = True
    for n in tree[v]:
        if visited[n] == False:	# 아직 탐색하지 않은 값이 있다면 자식에 해당
            ans[n] = v
            search(n)
    return

            
N = int(input())
tree = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)
ans = [0] * (N + 1)

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

search(1)	# 문제 조건: 노드는 1
for i in range(2, N + 1):
    print(ans[i])

자바

파이썬 코드와는 반대로, 이미 방문한 값이 있다면 현재 인덱스의 부모에 해당

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static ArrayList<Integer>[] tree;
    static boolean[] visited;
    static int[] parents;

    static void search(int i) {
        visited[i] = true;
        for (int t : tree[i]) {
            if (visited[t]) {
                parents[i] = t;
            }
            else {
                search(t);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        tree = new ArrayList[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < N + 1; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int n = 0; n < N - 1; n++) {
            int a = sc.nextInt();
            int b= sc.nextInt();
            tree[a].add(b);
            tree[b].add(a);
        }
        
        // 부모 찾기
        parents = new int[N + 1];

        search(1);
        for (int i = 2; i < N + 1; i++) {
            System.out.println(parents[i]);
        }

    }
}