https://www.acmicpc.net/problem/11725
import sys
from collections import deque
# with open('./data.txt', 'r') as file:
# data = file.read().strip()
# lines = data.split('\n') # 줄 단위로 나눔
# N = int(lines[0])
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N+1)]
maps = [0] * (N+1)
for i in range(1, N):
# a, b = map(int, lines[i].split())
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
def bfs():
Q = deque([1])
while Q:
a = Q.popleft()
for i in graph[a]:
if(maps[i] == 0):
maps[i] = a
Q.append(i)
bfs()
for i in range(2, N+1):
print(maps[i])
이번 문제를 풀면서 어느 쪽이 부모 노드인지 모르는 상황일 때 해결하는 방법에 대해서 배웠다.
인접리스트, 2차원 배열 두가지로 풀 수 있다고 한다.
인접리스트로 구현하면 순차탐색이 필요하고
2차원 배열로 구현하면 메모리낭비가 발생한다.
상황에 맞게 선택하면 될듯하다.
풀면서 왜 양방향으로 연결해줘야 될까 의문이었다.
GPT를 활용하며 생각해보니 그래야 다시 부모 노드로 올라가서 탐색할 수 있기 때문이다.
graph[a].append(b)
graph[b].append(a)input이 친절하게 연결된 모든 하위 요소들을 입력해주면 고맙지만 그렇지 않다. 이번 문제는 바로 연결이 뚝 끊기기 때문에, 5까지 내려갔다가
5 > 3 > 1 순으로 다시 올라가서 4를 찾아줘야한다.
이런식으로 어느게 부모인지 모르는 경우에는
양방향으로 해결하면 된다는걸 배웠다.
한-줄