백준 11725: 트리의 부모 찾기 - DFS(파이썬)

트리의 부모 찾기   성공

11725번: 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

내 코드

 

import sys
sys.setrecursionlimit(10**6) #**Recursion Error 방지!! **

def dfs(x):
    visited[x]=True #dfs 시작한 놈은 방문 처리

    for v in edge[x]: #x와 이어진 정점들을 탐색(x가 시작점인 간선)
        if not visited[v]: #그런 점들 중에 아직 방문 안했으면,
            answer[v]=x #x->v인 상황에서 x는 v의 부모!
            dfs(v) #dfs 가능


#메인 코드 부분
n=int(sys.stdin.readline())

edge=[] #간선 저장
visited=[] #정점별 방문 여부
answer=[] #특정 점의 부모 저장
for _ in range(n+1):
    edge.append([])
    visited.append(False)
    answer.append(0)

# **이 방식으로 edge를 표현하지 않으면 메모리 초과가 난다!!**
for _ in range(n-1):
    x,y=map(int, sys.stdin.readline().split())
    edge[x].append(y) #x-y 표현,
    edge[y].append(x) #y-x 표현

dfs(1) #트리는 다 이어져있기 때문에 루트인 1에서만 해도 모든 점 방문 가능

for i in range(2, n+1):
    print(answer[i])

 

풀이 및 접근)

- 루트가 1인 트리이므로 1부터 DFS를 하면 될거라고 생각했다.

- 여느 BFS와 동일하게 풀었는데 계속 메모리 초과 때문에 문제가 풀리지 않았다. edge[][]를 표현하는 방법에 문제가 있었다.

edge[x][y]=True, edge[y][x]=True 이런 식으로 간선을 표현하게 되면, N이 최대 100,000인데, N^2개의 리스트가 필요해서 메모리 초과가 났다.

- 이를 해결하기 위해 다른 방식으로 표현했다. edge[x].append(y), edge[y].append(x)와 같이 표현하면 메모리를 줄일 수 있다.

- 또, 이 문제의 그래프는 트리이기 때문에 다 이어져 있어서 한 점에서 시작하면 모두 탐색 가능하다. for문으로 모든 점을 돌며 방문여부를 따지면서 여러번 DFS를 시도하지 않아도 된다.