Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

28. 트리

대표적인 그래프 종류 중 하나인 트리를 다뤄 봅시다.

Java / Python

1. 트리의 부모 찾기

11725번

루트가 1인 트리가 주어질 때, 각 노드의 부모를 구하는 문제

이번 문제는 트리가 주어질 때, 각 노드의 부모를 구하는 문제입니다.
DFS(깊이 우선 탐색)를 통해서 탐색을 했습니다. 루트값이 1이므로 1부터 시작합니다.

• Java

import java.io.*;
import java.util.*;

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

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

		N = Integer.parseInt(br.readLine());

		list = new ArrayList[N + 1];
		parents = new int[N + 1];
		for (int i = 1; i <= N; i++)
			list[i] = new ArrayList<>();

		visit = new boolean[N + 1];

		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());

			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());

			list[s].add(e);
			list[e].add(s);
		}

		dfs(1);
		for (int i = 2; i <= N; i++)
			bw.write(parents[i]+"\n");

		bw.flush();
		br.close();
		bw.close();
	}

	public static void dfs(int v) {
		visit[v] = true;

		for (int i : list[v]) {
			if (!visit[i]) {
				parents[i] = v;
				dfs(i);
			}
		}
	}
}

• Python

import sys
sys.setrecursionlimit(10 ** 9)
 
N = int(sys.stdin.readline()) # 노드의 개수
tree=[[] for _ in range(N+1)]
for _ in range(N-1):
    s,e=map(int,sys.stdin.readline().split())
    tree[s].append(e)
    tree[e].append(s)

# 부모 저장
parents=[0 for _ in range(N+1)]
 
def DFS(start):
    for i in tree[start]: # 연결된 노드 모두탐색
        if parents[i]==0: # 방문 여부 - X 
            parents[i]=start # 부모노드 저장
            DFS(i)

DFS(1)
 
for i in range(2,N+1):
    print(parents[i])