[알고리즘/BFS & DFS] 2644번 : 촌수계산 - python

링크 : https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

---

• 문제
• 소요시간: 연습

---

• 설계하기(접근방법) 

1. 입력받기

요구사항을 입력받는다

 

2. 구현하기

사람의 번호를 넣으면

촌수를 계산해주는 bfs를 구현할 것이기 때문에

bfs(number) 방식으로 코드를 짜준다

 

인접리스트 방식으로 graph를 선언해주고

해당 num 의 bfs를 계산했을 때,

각각의 노드에 대한 가중치를 넣어주어야 하기 때문에

 

visited = [0] * (n+1) 방식으로 선언해준다

 

bfs 단계에 대해서 최소 가중치(최단 경로)를 넣어줄 것이기 때문에

if visited[near_node] ==0:

visited[near_node] = visited[num] + 1 로

갱신해준다

bfs는 단계적으로 파고들 것이기 때문에

항상 최단경로를 보장한다

 

 

 

 

3. 출력하기

최소 촌수를 계산해준다

 

 

---

• 코드(출력)

from collections import deque

def bfs(node) : 
    q = deque()
    q.append(node)
    while q:
        node = q.popleft()
        for n in graph[node]:
            if visited[n] == 0:
                visited[n] = visited[node] + 1
                q.append(n)


n = int(input())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
man_1, man_2 = map(int, input().split())

relation = int(input())
for i in range(relation):
    parent, kid = map(int, input().split())
    graph[parent].append(kid)
    graph[kid].append(parent)

bfs(man_1)

if visited[man_2] == 0 :
    print(-1)
else:
    print(visited[man_2])

---

• 얻어갈 부분

1. 문제의 요구사항을 bfs의 인자로 bfs를 구현하는 것을 연습했다.

2. bfs가 단계적으로 갈 것이기 때문에 visited가 0 이 아닐때 갱신하는 것이 항상 최단경로를 보장한다는 것을 알게 되었다

3. visited를 선언할 때, 0번 노드는 없지만 편리함을 위해 선언하면, [0] * (n + 1) 형태로 선언해야 함을 알게 되었다

4. bfs를 구현하는 경우 노드, 다음 노드, graph, visited 등 여러 구조를 사용하기 때문에 각각에 들어갈 요소들을 햇갈리면 안된다