[백준] 11725 - 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

문제 한줄 이해

-노드들의 부모트리 찾기

 

생각난 풀이

1번째 방법: 노드들의 연결 정보를 인접행렬로 나타내 bfs 탐색을 통해 확인 하려 했다.

이때 큐에 연결된노드와 현재 노드를 같이 넘겨주고 꺼낼때마다 visited에 방문을 표시할겸 부모노드의 번호로 바꿔줬다.

import sys
from collections import deque

n = int(sys.stdin.readline())
visited = [0] * (n+1)
graph = [[0 for i in range(n+1)] for i in range(n+1)]

for i in range(n-1):
    x,y = map(int,sys.stdin.readline().split())
    graph[x][y] = 1
    graph[y][x] = 1
    
def bfs(start,parents):
    que = deque()
    que.append((start,parents))
    visited[start] = parents
    
    while que:
        nowv,parents = que.popleft()
        visited[nowv] = parents
        
        for i in range(1,n+1):
            if visited[i] == 0 and graph[nowv][i] == 1:
                que.append((i,nowv))                
bfs(1,1)
for i in range(2,n+1):
    print(visited[i])

결과는 메모리 초과...

보통 나는 그래프의 정보를 담을때 인접행렬로 담아서 관리한다. 이유는 내가 직관적으로 보기 더 편했기 때문이다.

하지만 그래프의 크기가 커지면 그만큼의 메모리 공간이 필요하다는건 알고 있었다.

(그래프에서 보통 0,1 로 표현하기에 1비트만 필요하다. 그렇다면 100,000,000,000 비트 ÷ 8 = 12,500,000,000 바이트 약 12.5기가 바이트를 사용한다고 한다 ....)

실제로 이 문제에서 100000개의 노드가 있었고 인접행렬로 나타내면 메모리 초과가 나는 것이다.

 

2번째 방법: 그래서 인접리스트로 바꾸어 주었다. 

이유는 연결돼 있는 경우만 값을 추가 해주면 되기 때문에 메모리를 줄일 수 있는 것이다!

import sys
from collections import deque

n = int(sys.stdin.readline())
visited = [0] * (n+1)
graph = [[]for i in range(n+1)]

for i in range(n-1):
    x,y = map(int,sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)
    
def bfs(start,parents):
    que = deque()
    que.append((start,parents))
    visited[start] = parents
    
    while que:
        nowv,parents = que.popleft()
        visited[nowv] = parents
        
        for i in graph[nowv]:
            if visited[i] == 0:
                que.append((i,nowv))                
bfs(1,1)
for i in range(2,n+1):
    print(visited[i])