알고리즘💻/그래프(DFS&BFS)
BOJ 14496번: 그대, 그머가 되어
호프
2021. 5. 25. 03:17
https://www.acmicpc.net/problem/14496
14496번: 그대, 그머가 되어
첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 <= N <= 1,000, 1 <= M <= 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문자쌍
www.acmicpc.net
문제풀이:
BFS를 이용해서 간단하게 풀 수 있는 문제였다.
import sys
from collections import deque
a, b = map(int, sys.stdin.readline().split())
N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
n, m = map(int, sys.stdin.readline().split())
graph[n].append(m)
graph[m].append(n)
q = deque()
q.append(a)
visit = [False]*(N+1)
visit[a] = True
cnt = [-1]*(N+1)
cnt[a]=0
while (q):
n = q.popleft()
for i in graph[n]:
if (visit[i]==False):
visit[i] = True
cnt[i] = cnt[n]+1
q.append(i)
print(cnt[b])