[Python/BOJ] 백준 2644 촌수계산 (bfs)

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

2644번: 촌수계산

 

 

이전에 dfs 문제를 파이썬으로 풀어봐서 그런가 파이썬으로 bfs문제를 처음 풀어보았지만 그렇게 어렵지는 않았다.

 

 

문제 이름 그대로 촌수를 계산하는 문제이다. 

 

 

🖌 어떤 생각?

일단 파이썬으로 bfs문제를 처음 풀어보니 어떻게 해야할지 몰라서 코드를 찾아보았다.

 

deque을 이용해서 풀었다!

 

from collections import deque


n = int(input())
p,c = map(int, input().split())
m = int(input())
dist = [0]*(n+1)
arr = [[] for _ in range(n+1) ]

for i in range(m) :
    a,b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

def bfs(n) :
    queue = deque()
    queue.append(n)
    while queue :
        node = queue.popleft()
        for i in arr[node] :
            if dist[i]==0 :
                dist[i] = dist[node]+1
                queue.append(i)

bfs(c)
print(dist[p] if dist[p] >0 else -1)

 

 

🎨큰그림 

 

덱을 이용해 bfs의 인수로 들어온 사람과 인접한 사람들에 대해 for문을 돌린다.

for문을 돌리며 dist을 +1 씩 증가하여 촌수를 dist 배열에 저장한다. 

dist 배열에 저장된 사람은 다시 덱에 들어가서 그 사람과 인접한 사람은 다시 for문을 이용해 dist를 채운다. 

 

 

 

---

 

 

📈 자세한 코드 분석 

 

이미 c++ 로는 bfs를 어떻게 하는지 알고있기에 구조가 잘 보였다.

 

1.  deque

 

deque은 collections에 있다. 이를 import하여 사용한다. 

 

 

2. dist

저번 dfs에서는 visit을 사용하였지만 여기에 거리까지 생각해줘야하기에

dist라는 거리를 저장할 수 있는 리스트를 만든다. 

 

 

3. bfs 함수

deque에 넣을 때 사용하는 함수가 따로 이름이 다른것이 아니라 append로 list와 동일한것을 처음 알았다. 

popleft()는 이름만으로 기능을 알 수 있다. 가장 처음에 들어온것을 pop하는 것이다. 

 

이것과 연결된 사람들을 for문을 이용해 돌면서 dist[i]가 0이면 (즉, 촌수 계산을 하지않았다면)

이를 호출한 사람의 dist + 1 을 그사람의 dist에 저장한다.

그리고 덱에 넣는다. 

 

 

4. print

 

c++에서는 없으면 -1을 출력하라는 경우

if ( dist < 0) {
    cout<<-1;
}
else cout<<dist[p];

 

이런식으로 진행했어야했을텐데 파이썬에서는 한줄에 끝낸다.

 

print(dist[p] if dist[p]>0 else -1)

 

해당 값이 0보다 크다면 해당 값을 출력하고 아니면 -1을 출력하는 출력문이 간단해졌다.