알고리즘/백준

[BOJ/백준] 14496 그대, 그머가 되어 파이썬

개발싫어 2021. 10. 4. 23:49
728x90

문제 링크 : https://www.acmicpc.net/problem/14496

 

14496번: 그대, 그머가 되어

첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문

www.acmicpc.net

 

평범한 BFS 문제이다.

N이 최대 1000이므로 그래프 좌표를 인접 리스트로 하자.

 

from sys import stdin
from collections import deque

input = stdin.readline

s,e = map(int, input().split())
n,m = map(int, input().split())
adj_list = [[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int, input().split())
    adj_list[a].append(b)
    adj_list[b].append(a)

def solv():
    visited = [False]*(n+1)

    q = deque([(s,0)])
    visited[s] = True

    while q:
        now, cnt = q.pop()

        if now == e:
            print(cnt)
            return

        for nxt in adj_list[now]:
            if not visited[nxt]:
                visited[nxt] = True
                q.appendleft((nxt,cnt+1))
    print(-1)
solv()