[PS] BOJ 14496 / 그대, 그머가 되어

Minjun Kim

12 Jun 2025 • 3 min read

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

Thumbnail: Photo by Cody Chan (Unsplash)

썸네일은 문제랑 아무 상관 없지만, 문득 라멘이 먹고 싶어서 찾아왔습니다.

풀이

최단 거리 탐색하기

문제에서 문자 간의 치환으로 표현했지만, 결국 정점 \(a\)에서 \(b\)로 가는 최단 거리를 찾는 문제로 해석할 수 있습니다.

두 정점 사이의 최단 거리가 필요하기 때문에 다익스트라 기법을 사용해도 되지만, BFS로도 풀 수 있었다.

그래프 구현

지난번에는 인접 행렬로 구현했었으니, 이번엔 인접 리스트로 구현해봤습니다.

문제 조건에서도 정점은 최대 1,000개에 간선은 최대 10,000개이므로, 인접 행렬 방식에 비해 인접 리스트가 메모리 사용률에서 우수한 케이스이다.

N, M = map(int, input().strip().split())

adj_list: list[list[int]] = [[] for _ in range(N + 1)]  # 1번 인덱스부터 쓰기 위해 크기 + 1
for _ in range(M):
    u, v = map(int, input().strip().split())
    adj_list[u].append(v)
    adj_list[v].append(u)

인접 리스트로 구현한 그래프

BFS

큐에 다음에 탐색할 정점들을 넣고 반복하는 구성은 같다.

방문 여부를 계산할 check배열에 도달하기 위한 거리(치환 횟수) 를 같이 기록하도록 구현했다.

from collections import deque

queue = deque([A])
check = [0 for _ in range(N + 1)]
while queue:
    x = queue.popleft()
    for n in adj_list[x]:
        if check[n] == 0:
            queue.append(n)
            check[n] = check[x] + 1

BFS 코드

예외 처리

(1) A와 B가 같은 경우는 굳이 탐색할 필요 없이 답이 0으로 정해져 있다.

A, B = map(int, input().strip().split())
if A == B:
    print(0)
    exit(0)

A == B 일 때 예외 처리

(2) \(a\)에서 \(b\)로 도달하지 못할 경우 -1을 출력해야 한다.

다만, 앞서 check배열을 0으로 초기화했기 때문에 답을 check[B]로 출력할 시 0이라면 -1로 바꾸어 출력해 줄 필요가 있다.

아래 구문은 check[B]가 0이라면 or 뒤의 구문이 실행되기 때문에 가능하다.

print(check[B] or -1)

결과 출력

전체 코드

from collections import deque
input = open(0).readline
A, B = map(int, input().strip().split())
if A == B:
    print(0)
    exit(0)
N, M = map(int, input().strip().split())

adj_list: list[list[int]] = [[] for _ in range(N + 1)]  # 1번 인덱스부터 쓰기 위해 크기 + 1
for _ in range(M):
    u, v = map(int, input().strip().split())
    adj_list[u].append(v)
    adj_list[v].append(u)

queue = deque([A])
check = [0 for _ in range(N + 1)]
while queue:
    x = queue.popleft()
    for n in adj_list[x]:
        if check[n] == 0:
            queue.append(n)
            check[n] = check[x] + 1

print(check[B] or -1)

solution.py