[백준-실버2] 11725번 트리의 부모 찾기(파이썬, DFS 풀이)

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

 

<메모리 초과 해결>

- 처음 문제를 풀었을 때 메모리 초과가 떴다. (메모리 초과 코드는 맨 아래 첨부

- N이 100,000이기 때문에 이차원 배열을 사용하면 공간을 너무 많이 차지하기 때문

- 그래서 graph를 입력 받을 때 방법을 변경했다.

- 메모리 초과 코드는 2차원 배열을 전부 다 사용하고, 통과 코드는 연결 된 부분만 저장하는 배열이 된다

##### 메모리 초과 #####
graph = [[0]*(n+1) for _ in range(n+1)]
for _ in range(n-1):
    x, y = map(int, input().split())
    graph[x][y] = graph[y][x] = 1
    
    
##### 통과 코드 ######
graph = [[]*(n+1) for _ in range(n+1)]
for _ in range(n-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

 

<내 코드>

import sys
sys.setrecursionlimit(10**9)

input = sys.stdin.readline 
#입력
n = int(input()) #노드의 개수

graph = [[]*(n+1) for _ in range(n+1)]
for _ in range(n-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
visited = [False]*(n+1)
parents = [0]*(n+1) #각 인덱스 노드의 부모노드를 담는 배열

def dfs(v):
    visited[v] = True #방문처리
    
    for i in graph[v]:
        if visited[i] == False:
            visited[i] = True #방문처리
            parents[i] = v
            dfs(i)
            
for i in range(1,n+1):
    if visited[i] == False: #방문 안했으면
        dfs(i)

for p in parents[2:]: #2번 노드의 부모부터 출력
    print(p)

 

 

<시간 초과 코드>

import sys
sys.setrecursionlimit(10**8)

#입력
n = int(input()) #노드의 개수

graph = [[0]*(n+1) for _ in range(n+1)]
for _ in range(n-1):
    x, y = map(int, input().split())
    graph[x][y] = graph[y][x] = 1
    
visited = [False]*(n+1)
parents = [0]*(n+1) #각 인덱스 노드의 부모노드를 담는 배열

def dfs(v):
    visited[v] = True #방문처리
    
    for i in range(1, n+1):
        if visited[i] == False and graph[v][i] == 1:
            visited[i] = True #방문처리
            parents[i] = v
            dfs(i)
            
for i in range(1,n+1):
    if visited[i] == False: #방문 안했으면
        dfs(i)

for p in parents[2:]:
    print(p)