백준 11725 - 트리의 부모 찾기

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

 

먼저 예제 1번을 바탕으로 문제를 이해하면, 

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

 

(그리면서 풀면 더 쉽다..)

2번 노드 -> 4번

3번 노드 -> 6번

4번 노드 -> 1번

5번 노드 -> 3번

6번 노드 -> 1번

7번 노드 -> 4번

1번부터 N번까지의 노드가 있다. 

입력받은 인접한 두 노드를 트리로 완성하고, 각 노드의 부모가 누구인지 확인하는 문제이다.

import sys
sys.setrecursionlimit(10**6)
# input = sys.stdin.readline()

N = int(input())

adj = [[] for _ in range(N)] # 인접리스트
for i in range(N - 1) :
    a, b = list(map(int, input().split()))
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

사실 2번째 줄의 sys.setrecursionlimit을 적어주지 않아서 계속 RecusiveError 라는 런타임 에러를 뿜어냈다. (파이썬에도 재귀함수 제한이 있다니,,)

늘 문제를 풀듯이 N을 입력받고, 그래프를 통해서 adj 인접리스트에 각각의 노드들을 담아준다.

visit = [False] * (N + 1)
parent = [-1] * (N + 1)

나는 visit 배열과, 각각 부모가 누구인지 담을 parent 배열을 각각 선언했다. 

다른 사람들의 풀이를 보면, visit = [0] * (N + 1)로 하고, DFS를 수행하면서 visit != 0 일 경우에만 값을 바꿔주는 풀이도 확인했다.

# DFS
def dfs(u) :
    visit[u] = True
    for v in adj[u] :
        if not visit[v] :
            parent[v] = u
            dfs(v)

기본적인 DFS 의 구조를 통해서 짜주고, 방문하지 않은 노드일 경우에만 parent를 현재 노드의 값으로 변경했다.

이렇게 하면, 그래프에서 각 노드들의 부모를 확인 할 수 있다.

dfs(0)

for i in range(1, N) :
    print(parent[i] + 1)

실행 및 출력은 위와 같이.

 

# 백준 11725 - 트리의 부모 찾기
# 분류 : DFS

import sys
sys.setrecursionlimit(10**6)
# input = sys.stdin.readline()

N = int(input())

adj = [[] for _ in range(N)] # 인접리스트
for i in range(N - 1) :
    a, b = list(map(int, input().split()))
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

visit = [False] * (N + 1)
parent = [-1] * (N + 1)

# DFS
def dfs(u) :
    visit[u] = True
    for v in adj[u] :
        if not visit[v] :
            parent[v] = u
            dfs(v)
dfs(0)

for i in range(1, N) :
    print(parent[i] + 1)