새로운 접근 방법을 알 수 있어서 좋았던 문제.

1. 내 풀이: 실패

import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(k, m):
    visited[k] = 1
    for i in graph[k]:
        if i == m:
            print(k)
            return
        else:
            if visited[i] == 0:
                visited[i] = 1  
                dfs(i, m)

for j in range(2, n+1):
    visited = [0] * (n+1)
    dfs(1, j)

이 방법이 처음으로 내가 풀었던 방법이다. 그리고 결과는 ...

모두 시간 초과가 떴다.
일단 풀이 방법은 다음과 같다. 1번 노드부터 방문하게 되는데, 연결된 모든 노드를 돌면서 찾아야 하는 m(예를 들면 2 등등) 을 만나게 되면 해당 함수가 종료되면서 정답을 반환한다. 두 테스트 케이스에서는 통과한 방법이다.

그런데 시간 초과라니 ...
이런 접근 방법 말고는 떠오르지가 않아 바로 답을 봤다.

2. 다른 풀이

2-1. DFS

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())

graph = [[] for i in range(n+1)]

for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [0]*(n+1)

arr = []

def dfs(s):
    for i in graph[s]:
        if visited[i] == 0:
            visited[i] = s
            dfs(i)

dfs(1)

for x in range(2, n+1):
    print(visited[x])

풀이 출처: https://d-cron.tistory.com/22

이 분의 글에 가보면 내가 왜 틀렸는지 명확히 알 수 있다.
모든 노드를 탐색하는 방법은 노드를 탐색할 때마다 for문을 10만번씩 돌리기 때문에 최종적으로 연산을 100억번 해야 하기 때문이다. ^^
이렇게 수학적으로 계산하는 것도 정말 필요한 것 같다.

그래서 알게 된 새로운 방법은 바로 dfs 함수 부분이다.

def dfs(s):
    for i in graph[s]:
        if visited[i] == 0:
            visited[i] = s
            dfs(i)

여기서 기존과는 다르게 visited를 부모 노드, 즉 방문을 하게 된 원인의 노드로 채워주게 되는데, 이렇게 되면은 visited 리스트에는 부모 노드로만 꽉 차게 된다. 훨씬 간편한 방법 ...

2-2. BFS

import sys
from collections import deque

N = int(sys.stdin.readline())
graph = [[] for i 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)

queue = deque()
queue.append(1)

ans = [0]*(N+1)

def bfs():
    while queue:
        now = queue.popleft()
        for nxt in graph[now]:
            if ans[nxt] == 0:
                ans[nxt] = now
                queue.append(nxt)

bfs()
res = ans[2:]
for x in res:
    print(x)

이건 BFS 풀이 방법인데 개념은 유사하다.
대신 deque를 사용하게 된다는 것이 포인트!

3. 마치며

자꾸 자꾸 새로운 것을 알아가야 하는 그래프 ,,,
너무 흥미롭다.
그리고 시간 초과가 왜 났는지를 분석하면서 코드를 고치는 습관도 들여야 할 것 같다.