🔅코딩테스트 공부🔅/❗백준
[백준] 2644번 촌수계산(python)
윤무무
2023. 2. 11. 13:33
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
1. 내가 작성한 코드
from collections import deque
def bfs():
queue = deque()
queue.append(a)
visit[a] = 0
while queue:
x = queue.popleft()
if x == b:
return visit[x]
else:
for i in graph[x]:
if visit[i] == 0:
visit[i] = visit[x]+1
queue.append(i)
total = int(input()) #전체 사람 수
a,b = map(int, input().split())
family = int(input()) #부모 가족 수
graph = [[] for i in range(total + 1)]
visit = [0] * (total+1)
for i in range(family):
c,d = map(int, input().split())
graph[c].append(d)
graph[d].append(c)
bfs()
if visit[b] == 0:
print(-1)
else:
print(visit[b])BFS, DFS 모두 풀 수 있는 문제이다.
양방향 그래프라고 생각하고 문제를 해결하면 된다.