234. 트리의 부모 찾기

1) 어떤 전략(알고리즘)으로 해결?

• dfs, dfs 다 되지

2) 코딩 설명

<내 풀이>

import sys
sys.setrecursionlimit(10**5)
n = int(sys.stdin.readline().rstrip())
rel = {}
parent = [0 for _ in range(n+1)]

for j in range(1,n+1) :
    rel[j] = []

for i in range(n-1) :
    a,b = map(int, sys.stdin.readline().rstrip().split())
    # {1: [6, 4], 2: [4], 3: [6, 5], 4: [1, 2, 7], 5: [3], 6: [1, 3], 7: [4]} 
    # 나랑 관계 있는 애들 담아줌 
    rel[a].append(b)
    rel[b].append(a)

def dfs(idx) : #부모가 넘어옴 
    for r in rel[idx]  : #
        if parent[r] == 0 :
#부모가 등록 안된 애라면 (이미 등록된 애는 부모 등록 완료라 뭘 채우면 안됨)
            parent[r] = idx
            dfs(r)

dfs(1) 
# 1이 최상위 부모 -> 1의 자식부터 검사하면 그 밑의 자식들에게 부모 아이디 넘겨주면 됨
for p in range(2,n+1) :
    print(parent[p])

• pypy 로 해야지 근데 통과가 되더라

< 내 틀렸던 풀이, 문제점>

memory 초과 -> BFS 로 풀자

import sys

n = int(sys.stdin.readline().rstrip())
rel = list([0 for _ in range(n+1)] for _ in range(n+1))
visit =  [0 for _ in range(n+1)]
parent = [0 for _ in range(n+1)]

for i in range(n-1) :
    a,b = map(int, sys.stdin.readline().rstrip().split())
    rel[a][b] = 1
    rel[b][a] = 1
    
def dfs(idx) : 
    visit[idx] = 1
    for r in range(1,n+1) :
        if rel[idx][r]==1 and visit[r] == 0 :
            parent[r] = idx
            dfs(r)

dfs(1)

for p in range(1,n+1) :
    print(parent[p])

memory 초과 BFS,,,

from collections import deque
import sys

n = int(sys.stdin.readline().rstrip())
rel = list([0 for _ in range(n+1)] for _ in range(n+1))
parent = [0 for _ in range(n+1)]

for i in range(n-1) :
    a,b = map(int, sys.stdin.readline().rstrip().split())
    rel[a][b] = 1
    rel[b][a] = 1
    
def bfs(idx) : 
    q=deque()
    q.append(idx)

    while q : 
        now = q.popleft()
        for r in range(1,n+1) :
            if rel[now][r]==1 and parent[r] == 0 :
                parent[r] = now
                q.append(r)
                bfs(r)

bfs(1)

for p in range(2,n+1) :
    print(parent[p])

지금까지는 relation 을 2차원 배열에 저장함, 일차원에 해보자

import sys

n = int(sys.stdin.readline().rstrip())
rel = list([0 for _ in range(n+1)] for _ in range(n+1))
parent = [0 for _ in range(n+1)]

for i in range(n-1) :
    a,b = map(int, sys.stdin.readline().rstrip().split())
    rel[a][b] = 1
    rel[b][a] = 1
    
def dfs(idx) : 
    for r in range(1,n+1) :
        if rel[idx][r]==1 and parent[r] == 0 :
            parent[r] = idx
            dfs(r)

dfs(1)

for p in range(2,n+1) :
    print(parent[p])

런타임 에러! 메모리는 이차원 배열이 문제였군~

import sys

n = int(sys.stdin.readline().rstrip())
rel = {}
parent = [0 for _ in range(n+1)]

for j in range(1,n+1) :
    rel[j] = []

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

def dfs(idx) : 
    for r in rel[idx]  :
        if parent[r] == 0 :
            parent[r] = idx
            dfs(r)

dfs(1)

for p in range(2,n+1) :
    print(parent[p])

<반성 점>

메모리 초과가 나면 일차원 배열 / 사전으로 접근하자.

<배운 점>