[백준/11725] 트리의 부모 찾기 (bfs, python)

[백준/11725] 트리의 부모 찾기 풀이

bfs, python

 

1. 문제

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

---

2. 문제 해결 아이디어 

트리의 루트는 항상 1이다. 그러므로 첫번째 예제의 입력을 트리 그림으로 나타내면 다음과 같다.

 

1. 입력값으로 노드별로 연결된 노드를 저장하는 2차원 배열을 생성한다.

1.1. 추가로 부모 노드를 저장하기 위해, 각 노드의 개수 + 1 만큼 (0번은 제외할거라서) 0으로 채워진 1차원 배열을 생성한다. 

2. 1 ~ N번 (노드의 개수) 노드까지 완전탐색하면서, BFS를 수행한다.

2.1. BFS를 수행하면 1 -> 6 -> 4 -> 3 -> 2 -> 7 -> 5 순서로 이동하게 되는데,

현재 노드기준으로 자식 노드로 이동할때마다 부모 노드를 저장하는 배열에서 자식 노드의 인덱스에 부모 노드 값을 저장하면 된다.

그리고 방문 방문한 노드는 방문처리 해주면 된다. 

 

 

1. 초기화

N = int(input())
array = [[] for _ in range (N+1)] # 연결된 배열 저장 (0번 ~ 7번까지) 
parentsNodeArray = [0] * (N+1)
queue = deque([1])

 

 

초기 저장할 배열, 자식노드의 인덱스에 부모 노드를 저장하는 배열, BFS를 순회할 큐 생성

---

 

2. 입력 처리 

# 입력처리 : 이진트리이다. (루트는 1이다.)
for i in range(N-1):
    parents, child = map(int, input().split(' '))
    array[parents].append(child) # 부모-자식을 연결 
    array[child].append(parents) # 자식에도 부모와 연결되어 있다

 

양방향 트리로 입력을 해준다.  ( a->b, b->a 연결)

- 주어지는 입력은 방향이 없는 트리의 간선 정보이다.

- 만약 3,6이 들어오면 3-6이 연결되어 있다는 뜻이다.

- BFS는 루트(1번)에서 시작해서 자식 방향으로 내려가야 하므로, 부모와 자식이 연결돼있다는 정보가 양방향으로 저장되어야 탐색이 가능하다.

 

만약 입력이 아래와 같은데 단방향으로 저장하면, 아래와 같이 기존과 다른 그래프 연결 구조가 생겨버리기 때문이다. 

 

---

4. BFS를 이용하여 1번 ~ N번 노드까지 완전탐색 

while len(queue) > 0:
    nowNode = queue.popleft() # 현재 탐색할 기준 노드 꺼내기 
    # 현재 노드와 연결된 노드를 순회하며 큐에 넣는다.
    for childNode in array[nowNode]:
        if parentsNodeArray[childNode] != 0:
            continue
        queue.append(childNode) # 방문한 노드 큐에 넣기
        parentsNodeArray[childNode] = nowNode# 방문한 노드 부모 노드 업데이트
        

for i in range(2, N+1):
    print(parentsNodeArray[i])

BFS 연산을 queue를 이용하여 수행한다.

- QUEUE에 탐색하고자 하는 노드가 있을때까지 반복시키고, 

현재 노드와 연결된 자식 노드를 추가하면서,

자식 노드에 현재 노드(부모가됨)를 저장하기 위해 parentsNodeArray 변수에 저장한다. 

 

 

---

3. 코드

3-1. 파이썬 코드 (Python)

from collections import deque

N = int(input())
array = [[] for _ in range (N+1)] # 연결된 배열 저장 (0번 ~ 7번까지) 
parentsNodeArray = [0] * (N+1)
queue = deque([1])



# 입력처리 : 이진트리이다. (루트는 1이다.)
for i in range(N-1):
    parents, child = map(int, input().split(' '))
    array[parents].append(child) # 부모-자식을 연결 
    array[child].append(parents) # 자식에도 부모와 연결되어 있다 


# bfs를 이용하여 1번부터 탐색을 시작한다. 

while len(queue) > 0:
    nowNode = queue.popleft() # 현재 탐색할 기준 노드 꺼내기 
    # 현재 노드와 연결된 노드를 순회하며 큐에 넣는다.
    for childNode in array[nowNode]:
        if parentsNodeArray[childNode] != 0:
            continue
        queue.append(childNode) # 방문한 노드 큐에 넣기
        parentsNodeArray[childNode] = nowNode# 방문한 노드 부모 노드 업데이트
        

for i in range(2, N+1):
    print(parentsNodeArray[i])

# 방문처리 배열

 

 

---

 

4. 마무리