파이썬(python) 백준 14496 : 그대, 그머가 되어

14496번: 그대, 그머가 되어

문제 내용

시간 제한 : 2 초

메모리 : 512 MB

 

문자 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

 

예제 출력 1 

2

유형

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라

---

풀이

문제만 봐서는 이해가 안되는데 양방향 그래프 문제이다.

모든 간선 비용은 1

→ 가중치가 없는 최단경로 구하기 문제 = BFS (공식 암기하세요)

 

따라서 2가지 방법으로 풀이 가능하다.

1. 다익스트라
2. 너비우선탐색 (BFS)

BFS 풀이 시 주의할 점이 있다.

문제에서는 나와있지 않지만, 

a==b 이고, a→b 간선 정보가 주어지지 않은 경우

최소치환횟수는 -1이 아닌 0이 되어야 한다.

 

이 부분을 유의하지 않고 코드를 짜면 -1을 출력하여 오답을 받을 수도 있다.

설명이 다소 불친절한 문제라고 생각이 되다.

 

 

다익스트라 풀이

import sys, heapq
MAX = int(1e9)
a,b = map(int,sys.stdin.readline().split())
n,m = map(int,sys.stdin.readline().split())

board = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int,sys.stdin.readline().split())
    board[x].append(y)
    board[y].append(x)

dist_arr = [MAX]*(n+1)
dist_arr[a]=0
q = []
heapq.heappush(q, (0,a))
while q:
    dist, cur = heapq.heappop(q)
    if dist_arr[cur] < dist:
        continue

    for next in board[cur]:
        if dist_arr[next] > dist+1:
            dist_arr[next] = dist+1
            heapq.heappush(q, (dist+1,next))

if dist_arr[b] == MAX:
    print(-1)
else:
    print(dist_arr[b])

 

너비우선탐색 (BFS) 풀이

import sys, collections
MAX = int(1e9)
a,b = map(int,sys.stdin.readline().split())
n,m = map(int,sys.stdin.readline().split())

board = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int,sys.stdin.readline().split())
    board[x].append(y)
    board[y].append(x)

min_change_cnt = MAX
visited = [False]*(n+1)
visited[a] = True
q = collections.deque([(a,0)])
while q:
    cur,dist = q.popleft()
    if cur == b:
        min_change_cnt = min(min_change_cnt,dist)
    for next in board[cur]:
        if not visited[next]:
            visited[next] = True
            q.append((next,dist+1))

if min_change_cnt == MAX:
    min_change_cnt = -1
print(min_change_cnt)