(Python/파이썬) 백준 2644번 - 촌수계산

문제출처: https://www.acmicpc.net/problem/2644

2644번: 촌수계산

1. 코드

from collections import deque
import sys
 
N= int(input()) #사람 수
a,b = map(int, input().split()) #촌 수 계산 두 번호
M = int(input()) #관계 개수
 
graph = [ [] for i in range(N+1)] 
result=[0 for i in range(N + 1)] #결과 출력 리스트
 
def BFS(start): #시작부터 탐색
    q = deque()
    q.append(start)
    visited = [0 for i in range(N + 1)]
    visited[start] = 1
    while q:
        k = q.popleft()
        for i in graph[k]:
            if visited[i] == 0:
                visited[i] = 1
                result[i] = result[k] + 1
                q.append(i)
 
for i in range(M):
    x,y = map(int,input().split()) #부모 자식 관계 
    #양방향으로 값 넣어줌
    graph[x].append(y)
    graph[y].append(x)
 
BFS(a)
print(result[b] if result[b] != 0 else -1)
 

2. 해결과정

bfs를 활용해서 그래프를 탐색하고, 현재 탐색하는 노드와 연결된 노드에 현재 노드 값의 +1을 한다. 즉, 연결된 노드를 이동하는 것을 의미한다.

노드들의 탐색을 마치면 찾고자 하는 노드의 인덱스 값을 출력

 

3. 느낀점

bfs dfs 문제는 유형을 잘 모르겠다. 많이 풀어봐야지...