[ 그래프 이론-11725 ] 트리의 부모 찾기(Python)

---

접근법

 

단순히 현재 노드의 부모를 찾는거기 때문에, dfs(),bfs()없이 단순하게 해결할 수 있을 것 같아서 아래와 같이 접근했다.

import sys 

N = int(input())
visited = [0] * (N+1)
visited[1] = 1

for _ in range(N-1):
    x, y = map(int,sys.stdin.readline().split(" "))
    
    if visited[x] != 0:
        visited[y] = x
    
    else:
        visited[x] = y
        
for i in range(2,N+1):
    print(visited[i])

 

입력받는 두 수 중 하나는 무조건 이전에 언급된 노드여야 루트가 1인 트리를 형성할 수 있다.

따라서 입력받음과 동시에 두 수 중 방문되었던 노드가 있다면 다른 노드는 방문했던 노드의 자식이 되기 때문에 visited[]에 부모의 노드를 입력하고 이를 출력하도록 하도록 하였다.

예제문제는 모두 통과 되었지만 틀린 답으로 처리되어서 결국 dfs()로 해결하였다.

 

입력받는 두 노드 사이의 연결 상태를 graph 이중 배열에 저장하고 1부터 시작해서 dfs() 알고리즘을 적용한다. 이때, 방문하지 않은 노드에 대하여 visited[]에 부모 노드를 저장하고 이를 출력한다.

---

정답

import sys 
sys.setrecursionlimit(10**9)


N = int(input())
visited = [0] * (N+1)
graph = [[]for _ in range(N+1)]

for _ in range(N-1):
    x, y = map(int,sys.stdin.readline().split(" "))
    graph[x].append(y)
    graph[y].append(x)
        
def dfs(i):
    for j in graph[i]:
        if visited[j] == 0:
            visited[j] = i
            dfs(j)
            
dfs(1)
            
for i in range(2,N+1):
    print(visited[i])

 

dfs()의 parameter i는 1(루트)부터 시작하는 부모 노드가 들어온다. 그리고 for문을 graph[i]에 대하여 돌기 때문에 j에는 자식 노드들이 들어가게 된다. 따라서 방문하지 않은 자식 노드들에 대하여 부모 노드가 i임을 visited[]에 저장함으로써 확인하고 이를 출력한다.