문제 설명
이번 포스팅은 백준 11725번: 트리의 부모 찾기 문제 풀이에 대한 기록입니다.
문제를 간단히 요약하면, "어느 쪽이 부모, 자식인지 모르는 연결된 정점 쌍들의 정보가 주어졌을 때, 이를 통해 트리를 구성하여 각 정점들의 부모를 알아내는 문제" 입니다.
풀이
1. 연결된 정점들의 정보를 저장하는 방법
우리는 연결된 두 정점의 쌍을 N-1개 입력받습니다.
두 정점이 연결되어있음을 저장하는 방법은, 크게 두 가지 입니다.
- 각 정점마다 linked list를 두어, 자신과 연결된 정점들을 저장
- 장점 : 연결된 정점들만큼만 공간이 필요하므로 공간의 낭비가 적음
- 단점 : 특정한 두 정점 간의 관계를 확인하기 위해선 순차탐색 필요
- N*N의 2차원 배열을 선언하여, 연결된 두 정점에 해당하는 위치에 연결되어있음을 표시하여 저장
- 장점 : 특정한 두 정점 간의 관계를 확인하기 위해 index로 즉시 접근 가능
- 단점 : 연결 여부에 관계없이 N*N의 2차원 배열을 할당하므로, 공간 낭비 발생
이 문제에서 정점의 개수 N의 범위는 **최대 100,000개** 입니다.
2번 방법을 사용하면 최대 100,000 * 100,000의 2차원배열을 선언해야 하므로 메모리가 매우 많이 사용됩니다.
또한 입력받는 연결된 두 정점 쌍은 N-1개이므로 메모리 낭비를 줄이기 위해 1번 방법을 사용하는 것이 바람직합니다.
vertices = [[0] for _ in range(N+1)] # 연결 정보를 저장할 linked list의 배열또 하나 고려해야 할 것은, 두 정점 중 어느 쪽이 부모이고 자식인지 아직은 알 수 없습니다.
즉, 두 정점이 indirect하게 연결되어 있다는 의미입니다.
indirect하게 연결된 두 정점 간의 연결 정보는 서로의 linked list에 둘 다 저장해주어야 합니다.
for _ in range(N-1):
a, b = map(int, input().split())
# 두 정점의 linked list에 각각 저장
vertices[a].append(b)
vertices[b].append(a)2. 연결된 노드 정보들을 하나씩 탐색하며 부모-자식 관계 확인
연결된 정점들의 정보를 모두 저장했으니, 이제 이것들을 하나씩 보면서 정점들의 부모-자식 관계를 밝혀나가면 됩니다.
문제에서 "트리의 루트를 1이라고 정했을 때" 라는 가정이 있습니다.
따라서 루트인 1과 연결된 정점들은 반드시 부모가 1인 자식 노드들이 됩니다.
트리에서 루트를 제외한 모든 노드들은 하나의 부모만을 가집니다.
즉, 1의 자식이라고 밝혀진 정점들은 이미 부모가 있기 때문에, 이 정점과 연결된 다른 정점들은 모두 이들의 자식 노드일 수 밖에 없습니다.
이런 식으로, 1부터 시작하여 1의 자식인 정점들을 찾아내고 다시 이들의 자식인 정점들을 찾아가는 방식 으로 모든 정점들의 부모-자식 관계를 밝혀낼 수 있습니다.
parent = [0]*(N+1) # 각 노드들의 부모를 기록하는 배열
parent[1] = 0
q = deque()
q.append(1)
while q:
current = q.popleft()
for v in vertices[current]:
# 이미 parent에 기록되었다는 것은 부모가 있다는 뜻
# 이 정점과 연결된 것들은 자식이 됨
if parent[v] == 0:
parent[v] = current
q.append(v)이렇게 모든 정점들의 부모 노드를 밝혀내었다면 차례로 출력하면 끝입니다.
이때 아래와 같이 단순하게 출력해도 되지만,
for p in parents[2:]:
print(p)최대 100,000-1번 출력하는 경우가 있기 때문에, 아래와 같은 방식으로 한번에 출력함으로써 시간을 조금 줄일 수 있습니다ㅎㅎ
print('\n'.join(map(str, parent[2:])))
요 정도 차이 나는데, 메모리까지 고려하면 그닥 큰 차이가 없는 것 같기도...
어쨌든 문제 해결!!
결과 코드
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
vertices = [[0] for _ in range(N+1)]
parent = [0]*(N+1)
for _ in range(N-1):
a, b = map(int, input().split())
vertices[a].append(b)
vertices[b].append(a)
parent[1] = 0
q = deque()
q.append(1)
while q:
current = q.popleft()
for v in vertices[current]:
if parent[v] == 0:
parent[v] = current
q.append(v)
print('\n'.join(map(str, parent[2:])))