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