https://www.acmicpc.net/problem/14496
시간 2초, 메모리 512MB
input :
- 바꾸려 하는 문자 a와 b
- 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M(1 <= N <= 1,000, 1 <= M <= 10,000)
- 치환 가능한 문자쌍
output :
- a를 b로 바꾸기 위해 필요한 최소 치환 횟수를 출력한다. 치환이 불가능한 경우는 –1을 출력한다.
일단 맨 처음 input을 잘못 읽었다...
EOF 문제인줄 알고 하다가 value 에러를 얻어맞고, a == b의 경우를 따져줘야 하기 때문에 이 경우에는 바로 0을 출력하도록 한다.
그리고 최단 기간을 찾는것이기 때문에 그냥 BFS를 이용하자.
괜히 DFS로도 만들어 보려다가 힘만 뺐다.
BFS로 가장 먼저 b를 만나는 경우가 최단기간이니까 그럴 때 반복문 멈추고 나오도록 하자.
import sys
from collections import deque
a, b = map(int, sys.stdin.readline().split())
n, m = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
one, two = map(int, sys.stdin.readline().split())
graph[one].append(two)
graph[two].append(one)
if a == b:
print(0)
exit()
visit = [0] * (n + 1)
visit[a] = 1
q = deque([(a, 0)])
while q:
now, cnt = q.popleft()
for next_node in graph[now]:
if next_node == b:
print(cnt + 1)
exit()
if visit[next_node] == 0:
visit[next_node] = 1
q.append((next_node, cnt + 1))
print(-1)
