[Python] 백준/BOJ 11725번: 트리의 부모 찾기 (Silver 2)

💻 Problem

문제 보러 가기

 

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

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

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

 

💡 Approach

사실 처음에는 복잡하게 생각해서 코드 짜기 헷갈렸다...

2번부터 n번까지의 노드를 출력하려면 2 ~ n 반복문으로 탐색 함수를 돌려서 각 결과를 출력하는 건 줄 알았다.

그래서 연결된 노드 중에 루트 노드가 있으면 루트 노드가 부모 노드이고.. 연결된 노드가 하나이면 연결된 노드가 부모 노드이고.. 이런 조건문을 달아줬었고

탐색하려는 노드와 연결된 각 노드들이 자식 노드인지 부모 노드인지 판별해야 한다고 생각했다.

 

근데 그냥 단순 dfs 문제였당 ㅎㅎ

왜 이렇게 복잡하게 생각하고 있었나 약간 허무!

생각해 보니 루트 노드에서부터 쭉 내려가면 어떤 게 부모 노드이고 어떤 게 자식 노드인지 알 수 있었담..

 

일단 간선 정보를 입력받을 때는 어떤 게 부모 노드이고 어떤 게 자식 노드인지 모르니 양방향으로 그래프를 만들어야 한다.

 

자 그럼 dfs로 탐색 시작~~~~

루트 노드인 1부터 시작한다!

 

dfs 함수에서 현재 탐색 중인 노드는 부모 노드이다!

이 부모 노드의 자식 노드들을 찾아 몇 번 노드의 자식 노드인지 기록해 줄 것이다.

이를 위해 방문 처리 배열(visited)을 만들어뒀는데, 여기서 방문 처리뿐만 아니라 부모 노드 번호까지 기록해 준다.

기본적으로 0으로 세팅해 뒀기에 아직 방문하지 않은 노드면 visited[child]가 0일 것이고, 이미 방문한 노드면 visited[child]에 부모 노드 번호가 기록되어 있을 것이다.

 

모든 탐색이 완료되었다면 visited의 각 노드에 부모 노드 번호가 기록되어 있을 것이다.

visited를 출력하면 끝!

 

예제 입력 1

그림으로 그리면서 이해했다~

 

✏️ Solution

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

def dfs(parent):
    # 부모 노드와 연결된 자식 노드들을 탐색한다
    for child in graph[parent]:
        # 아직 방문하지 않은 노드면 방문한다다
        if not visited[child]:
            # 부모 노드와 연결된 자식 노드를 방문 처리한다
            # 방문 처리에는 T/F가 아닌 자신의 부모 노드 번호를 기록한다
            visited[child] = parent
            dfs(child)

n = int(input())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)

# 간선 정보로 그래프 만들기
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dfs(1)
print(*visited[2:], sep='\n')

이전에 dfs 문제 (18126. 너구리 구구)를 풀 때 sys.setrecursionlimit()을 설정해야 한다는 걸 알게 되었는데 이번에도 dfs로 풀었으니 이를 설정해야 했다.

노드의 개수가 곧 트리의 최대 깊이인데 n의 최댓값이 10 ^ 5이므로 재귀 깊이 또한 10 ^ 5로 세팅했다.

 

⏱️ 시간복잡도

• O(n)

노드의 개수와 간선의 개수를 더하면 n + (n - 1)이다.

즉, 2n - 1이므로 n의 최댓값인 100,000(10 ^ 5)을 대입하면 2 * 10 ^ 5 - 1이다.