[Python] 14496번 그대, 그머가 되어

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

14496번: 그대, 그머가 되어

---

 

22/10/08

 

 

단순 BFS문제이다.

---

 

문제 접근 방식:

 

 

이 문제에서 요구하는 바는 a를 b로 바꾸기 위해 필요한 최소 치환 횟수이다.

 

결국 어느 정점에서 다른 한 정점으로 가는 최소 거리를 구하는 문제와 별 다를 바가 없으므로, BFS로 해결할 수 있다.

 

구현하는데 주의할 점은 행렬과 같이 주어진 그래프와는 다르게 실제 간선으로 그래프가 주어져서, 그 부분만 조금 고치면 쉽게 구현할 수 있다.

 

또한, 바꿀 수 없을 때 -1을 출력한다는 점만 주의하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 14496번 그대, 그머가 되어
# 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
어느 한 정점에서 다른 정점으로 가는 최소 거리를 구하는 문제이므로
BFS로 풀 수 있다.
'''
from collections import deque
import sys
input = sys.stdin.readline

start, end = map(int, input().rstrip().split())
total_node_num, total_edge_num = map(int, input().rstrip().split())

graph = [[] for _ in range(total_node_num + 1)]
visited = [0 for _ in range(total_node_num + 1)]
for _ in range(total_edge_num):
    node1, node2 = map(int, input().rstrip().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

queue = deque()
queue.append((start, 0))
visited[start] = 1
flag = True
while queue:
    now_node, time = queue.popleft()
    if now_node == end:
        print(time)
        flag = False
        break
    for node in graph[now_node]:
        if visited[node] == 0:
            visited[node] = 1
            queue.append((node, time+1))
if flag:
    print(-1)