이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 그래프를 인접 리스트 방식으로 저장하였다. 이때 치환이 양방향으로 가능하기 때문에 양방향으로 모두 저장해줘야 한다. 그리고 BFS를 처리하기 위해 사용할 큐 q는 최소힙으로 선언하고, 초기에 0, a를 넣어준다. 이때 0은 치환 횟수가 되고, a는 현재의 문자를 의미한다. a가 시작 문자이므로 a를 넣어주었다. while문에서는 q에서 치환 횟수와 현재 문자를 추출해주고, 이때 현재 문자가 b와 같다면 정답을 치환 횟수로 갱신해주었다. 그 외에는 각각의 그래프를 순회하며 q에 치환 횟수+1과 다음에 올 문자를 넣어주도록 하였다. 마지막으로 결과를 출력했다.

이렇게 접근하였을 때, 메모리 초과가 발생하였다. 그래서 찾아본 결과 방문 처리를 하지 않으면 사이클이 있을 경우에 무한대로 돌기 때문에 방문 처리를 적용해 주어야 한다는 사실을 알게 되었다. 그래서 방문 처리를 매 반복마다 해주었고, 이미 방문했던 문자일 경우에는 건너 뛰도록 다시 작성하였다.

이번에는 90%가 넘어가서 오답 처리되었다. 생각해보니 문자를 원하는 문자로 치환하지 못하는 경우도 발생할 수 있다는 것을 깨달았고 문제를 다시 읽어보니 치환할 수 없을 경우에는 -1을 출력하라는 문장이 보였다. 그래서 결과값이 초기에 설정한 값과 일치할 경우에는 -1을 출력하도록 코드를 수정하였다.

• a, b를 입력받는다.
• n, m을 입력받는다.
• 그래프로 사용할 리스트 graph를 n+1개의 2차원 리스트로 선언한다.
• m번 반복하는 for문을 돌린다.
  -> frm, to를 입력받는다.
  -> graph[frm]에 to를 넣는다.
  -> graph[to]에 frm을 넣는다.
  (양뱡향으로 저장)
• 결과를 저장할 변수 result를 sys.maxsize로 선언한다. (최솟값을 찾아야 하므로)
• 방문 처리에 사용할 리스트 visited를 False n+1개로 채운다.
• BFS에 사용할 큐 q를 최소힙으로 선언하고 (0, a)를 넣는다.
• q가 있을 동안 반복하는 while문을 돌린다.
  -> cnt, cur을 q에서 추출한다. (cnt는 치환 횟수, cur은 현재 문자)
  -> 만약 cur이 b와 같다면, result를 result와 cnt 중 더 작은 값으로 갱신하고, while문을 종료한다.
  -> 만약 visited[cur]이 False일 경우,
  --> visited[cur]을 True로 갱신한다.
  --> graph[cur]을 순회하는 to에 대한 for문을 돌린다.
  ---> tmp를 cnt+1로 저장한다.
  ---> q에 (tmp, to)를 넣는다.
• 만약 result가 sys.maxsize일 경우, -1을 출력한다.
• 그 외에는 result를 출력한다.

Code

import heapq
import sys
a, b=map(int, input().split())
n, m=map(int, input().split())
graph=[[] for _ in range(n+1)]
for _ in range(m):
    frm, to=map(int, input().split())
    graph[frm].append(to)
    graph[to].append(frm)
result=sys.maxsize
visited=[False for _ in range(n+1)]
q=[]
heapq.heappush(q, (0, a))
while q:
    cnt, cur=heapq.heappop(q)
    if cur==b:
        result=min(result, cnt)
        break
    if not visited[cur]:
        visited[cur]=True
        for to in graph[cur]:
            tmp=cnt+1
            heapq.heappush(q, (tmp, to))
if result==sys.maxsize:
    print(-1)
else:
    print(result)