[알고리즘] 백준 2644번 촌수계산
🚲

[알고리즘] 백준 2644번 촌수계산

Created
2022/07/28
Tags
Algorithm
Python
BFS
 
2022-07-28 @이영훈
 
 

접근방법

그래프 문제입니다. 시작 노드에서 도착 노드까지 최단거리를 구하는 문제이기 때문에 BFS로 접근하여 문제를 풀었습니다.
 
graph 변수에 연결되어 있으면 양방향으로 이동할 수 있게 graph[x][y] = 1, graph[y][x] = 1로 설정하였습니다. 자식에서 부모로 갈수도 있고, 부모에서 자식으로 갈 있도록 하기 때문입니다.
큐(Queue)에 시작 노드와 초기 cost = 0을 tuple로 넣었습니다.
그리고 visited 변수로 방문한 적이 있는 지 확인하였습니다.
 
 

파이썬 코드

Python
import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
start_node, end_node = map(int, input().split())
m = int(input())

graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

# (node, cost)
queue = deque([(start_node, 0)])
visited = [False] * (n + 1)

while queue:
    node, cost = queue.popleft()
    for target in range(n + 1):
        if graph[node][target] == 1 and not visited[target]:
            if target == end_node:
                print(cost + 1)
                exit(0)

            graph[node][target] = cost + 1
            visited[target] = True
            queue.append((target, cost + 1))

print(-1)