✔ 풀이를 위한 아이디어
- 그래프 (Graph) 탐색 (DFS, BFS)
- 트리 (Tree) 개념 이해
✔ 수정 전 코드 [시간 초과]
import sys
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
stack = [1]
visited = []
ans = [-1]*(N+1)
while stack:
tmp = stack.pop()
if tmp not in visited:
visited.append(tmp)
child = list(set(graph[tmp]) - set(visited))
stack += child
for c in child:
ans[c] = tmp
for i in range(2, N+1):
print(ans[i])- 문제에 대한 설명이 부족해서, 문제 이해에 시간이 조금 걸리긴 했지만 해결은 간단하다.
- 그래프 탐색 문제라고 봐도 무방할 정도이다. 다만 그래프를 트리처럼 생각해야하기 때문에 트리의 개념 정도는 알고 있어야 할듯. (DFS와 BFS로 모두 풀 수 있다!)
- 루트를 1로 가정했기 때문에 1부터 순회한다. 트리로 생각하면 부모 노드부터 방문하기 때문에 자신과 연결된 노드 중 아직 방문하지 않은 노드는 모두 자식 노드이다. 따라서 Stack에 push할 때 자신과 연결된 노드들 중 아직 방문하지 않은 노드들에게 자신이 부모 노드라는 정보를 넣어준다.
- 다만 N의 범위가 꽤나 크다보니 visited 배열을 선언하여 관리하면서, tmp가 visited 배열 안에 있는지 탐색하는 방법은 시간 초과를 불러왔다. (저렇게 set로 만들어서 처리하는 것도 Python 내부적으로 별로 효율적이지 못한 시간복잡도를 가지고 있는 듯 하다.)
✔ 수정 후 코드
import sys
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
stack = [1]
visited = [0]*(N+1) # 배열의 탐색이 아닌, index로 바로 확인 가능
ans = [-1]*(N+1)
while stack:
tmp = stack.pop()
if not visited[tmp]: # 이전의 not in visited 보다 시간복잡도가 낮다
visited[tmp] = 1
child = []
for i in range(len(graph[tmp])): # 트리이기 때문에 최대 간선의 갯수가 3이고,
if not visited[graph[tmp][i]]: 따라서 시간복잡도가 그리 높지 않다.
child.append(graph[tmp][i])
stack += child
for c in child:
ans[c] = tmp
for i in range(2, N+1):
print(ans[i])- 시간 초과 문제를 해결하기 위해서 위처럼, visited 배열을 미리 선언하고 index를 활용해 관리하는 방식을 선택하였다.
- 사실 이전에 사용한 방법은 일반적인 그래프 구조에서는 더 효율적일지도 모른다. 하지만 이 문제처럼 트리인척 하는 그래프(?)는 간선의 갯수가 최대 3개로 한정되므로 이 방식이 효율적인 것 같다. (백준의 채점 기준도 이에 맞춰서 설정된 듯 하다.)
- 혹시 PyPy3로 채점이 될까 하여 두 번씩 채점해봤었는데, 어림도 없었다. 어떤 방법을 택할지는 문제 상황에 맞추도록 하자.
- 첫번째로 맞았다고 나온 코드는 if tmp not in visited를 실수로 수정하지 않고 돌린건데 통과가 되었다. 앞으론 꼼꼼하게 확인하고 제출하자.
✔ 관련 개념 (참고 링크)
- Grpah 를 트리 Tree 처럼 생각하기
