[BOJ][⚪1][백준#14496] 그대, 그머가 되어

문제 출처

BAEKJOON Online Judge #14496

문제

선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 3년 내내 공부만 했기 때문에, 요즘 학생들이 사용하는 ‘야민정음’에 대해서는 문외한이다. 친구들의 대화에 끼고 싶은 대호는 야민정음을 공부하기로 했다. 야민정음이란, 비슷한 모양의 글자를 원래 문자 대신에 사용하는 것을 일컫는다. 예를 들어, ‘그대’는 ‘그머’로, ‘팔도비빔면’은 ‘괄도네넴댼’으로, ‘식용유’는 ‘식용윾’으로, ‘대호’는 ‘머호’로 바꿀 수 있다. 아무 문자나 치환할 수 있는 건 아니며 치환이 가능한 몇 개의 문자들이 정해져있다. 예를 들어보자. (a, b), (a, c), (b, d), (c, d)가 주어지는 경우, a를 d로 바꾸는 방법은 a-b-d, a-c-d로 2개가 있다. (a, b), (b, c), (a, c)가 주어지는 경우, a를 c로 바꾸는 방법은 a-b-c, a-c의 2개가 있다. 하지만 이 경우에는 치환횟수에 차이가 생기게 된다. 머호는 문자 a를 문자 b로 바꾸려하고, N개의 문자와 치환 가능한 문자쌍 M개가 있다. 머호에게 a를 b로 바꾸기 위한 치환의 최소 횟수를 구해서 머호에게 알려주자! 프로그램 작성의 편의를 위해, 머호가 공부하는 모든 문자는 자연수로 표현되어 주어진다.

입력

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

출력

a를 b로 바꾸기 위해 필요한 최소 치환 횟수를 출력한다. 치환이 불가능한 경우는 –1을 출력한다.

예제

예제 1

입력

1 2
4 4
1 3
1 4
3 2
4 2

출력

2

예제 2

입력

2 3
3 3
1 2
1 3
3 2

출력

1

My Sol

import sys
input = sys.stdin.readline
from collections import deque

def main():
    a, b = map(int, input().split())
    N, M = map(int, input().split())
    G = [[] for _ in range(N+1)]
    for _ in range(M):
        s, e = map(int, input().split())
        G[s].append(e)
        G[e].append(s)

    Q = deque([[a, 0]])
    visit = [0]*(N+1)
    ret = 1e9
    while Q:
        u, d = Q.popleft()
        if u == b:
            ret = min(ret, d)
        for v in G[u]:
            if visit[v]: continue
            visit[v] = 1
            Q.append([v, d+1])

    return -1 if ret == 1e9 else ret

print(main())

그래프 문제인데, 다익스트라를 사용해서 가중치를 1로 부여해도 되고 BFS를 통해 최단거리를 구해도 되는 문제였다. deque에 시작문자 a와 치환횟수 0을 넣는다. 그리고 Q에 원소가 없을 때까지 반복을 진행한다.

반복은 원소의 값이 목표한 문자라면, 치환횟수 d와 ret 중 더 작은 값을 ret에 갱신한다. 그리고 u와 치환할 수 있는 모든 v에 대해 visit 체크 이후 Q에 넣는다.

만약 이 반복을 모두 마친 뒤에도 ret이 최초값인 1e9라면 이는 치환이 되지 않은 것이므로 -1을 출력하고, 그것이 아니라면 ret을 출력한다.

결과

맞았습니다!!

최초에 len(Q)를 통해 인접한 치환문자에 대해 사이클을 반복하며 최단거리를 BFS로 풀어내보려 했는데, 로직상 맞는데 계속 틀렸다고 나와서 너무 멘붕이었다. 아직도 이 오답의 이유를 알 수가 없다.

모범답안

출처

import sys
input = sys.stdin.readline


def bfs():
    Q = [a]
    visited = [0] * (N + 1)
    visited[a] = 1

    while Q:
        curV = Q.pop(0)
        if curV == b: return visited[curV] - 1
        for nexV in adj[curV]:
            if not visited[nexV]:
                Q.append(nexV)
                visited[nexV] = visited[curV] + 1

    return -1


a, b = map(int, input().split())
N, M = map(int, input().split()) 
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

print(bfs())

연산시간과 풀이가 조금 짧은 풀이를 발견해 분석해보려 한다. visited를 단순히 예아니오의 여부가 아닌, 최단거리로 취급하였다. 만약 visited에 값이 없다면 해당 값에 도달한 첫 치환이므로 이때의 최단거리를 visited에 체크하고, Q에 해당하는 값을 넣는다.