이번 문제는 깊이우선탐색을 통해 해결하였다. 처음에 이 문제에 접근할 때에는 dfs 재귀함수를 통해 각 노드의 레벨을 저장하고 2중 for문을 통해 현재 노드와 연결된 노드의 레벨이 현재 노드의 레벨보다 1 낮을 경우 출력하는 방법으로 접근하였다.

def dfs(cur):
    visited[cur]=True
    for i in range(1, n+1):
        if tree[cur][i]==1 and visited[i]==False:
            level[i]=level[cur]+1
            dfs(i)
n=int(input())
tree=[[0]*(n+1) for _ in range(n+1)]
for _ in range(n-1):
    a, b=map(int, input().split())
    tree[a][b]=1
    tree[b][a]=1
level=[0 for _ in range(n+1)]
visited=[False for _ in range(n+1)]
dfs(1)
for i in range(2, n+1):
    for j in range(1, n+1):
        if tree[i][j]==1 and level[i]-1==level[j]:
            print(j)

이 방법으로 문제는 잘 해결되었지만 메모리 초과 오류가 발생하였다. 여러가지 방법을 생각해보다가 결국은 다른 사람들의 풀이를 살펴보게되었다.

본인의 풀이의 경우 tree를 0으로 모두 채워두고 간선이 있을 경우에 1로 갱신하는 방식으로 tree를 저장하였다. 그러나 다른 사람들의 풀이에서는 각 노드와 연결된 노드를 리스트에 넣는 방식으로 저장하였다. 이렇게 하면 실제로 노드들이 연결된 것처럼 순차적으로 노드를 따라갈 수 있다는 것을 깨달았다. 이 방법으로 tree를 구현하고 dfs 재귀함수에서는 현재 노드와 연결된 노드들을 담아 둔 리스트를 순회하면서 연결된 노드 i의 부모가 없다면 i의 부모를 현재 노드로 지정해주고 dfs를 재귀호출 하는 방식으로 하여 곧바로 부모 노드를 저장하는 방식으로 풀이하였다. 이 문제에서도 재귀 에러가 발생하여 sys.setrecursionlimit(10**9)를 적용해주었다.

• 최대 재귀 제한을 늘려준다.
• dfs함수를 cur, tree, parents를 인자를 갖도록하여 선언한다.
  -> tree[cur]을 순회하는 i에 대한 for문을 돌린다.
  --> 만약 parents[i]가 0이라면 (부모가 지정되어있지 않다면),
  ---> parents[i]를 cur로 갱신한다.
  ---> dfs(i, tree, parents)를 재귀호출한다.
• n을 입력받는다.
• tree를 2차원 리스트로 선언한다.
• 인덱스의 부모를 저장하는 리스트 parents를 0 n+1개로 선언한다.
• n-1번 반복하는 for문을 돌린다.
  -> a, b를 입력받는다.
  -> tree[a]에 b를 넣는다.
  -> tree[b]에 a를 넣는다.
• dfs(1)을 호출한다.
• 2부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> parents[i]를 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(cur, tree, parents):
    for i in tree[cur]:
        if parents[i]==0:
            parents[i]=cur
            dfs(i, tree, parents)
n=int(input())
tree=[[] for _ in range(n+1)]
parents=[0 for _ in range(n+1)]
for _ in range(n-1):
    a, b=map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
dfs(1, tree, parents)
for i in range(2, n+1):
    print(parents[i])