백준 12851번: 숨바꼭질 2 + 13913번: 숨바꼭질 4

이전에 풀었던 백준 1697번 숨바꼭질 문제에 추가적인 조건이 추가된 두 문제를 풀어보았다. https://velog.io/@dlehdtjq00/백준-1697번-숨바꼭질

1. 백준 12851번: 숨바꼭질 2

• 추가된 조건: 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

✔ 숨바꼭질 2 정답 코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
MAX = 10 ** 5
dist = [0] * (MAX+1)
count = [0] * (MAX+1)  # count 배열을 새로 만들어주었음

queue = deque([N])
count[N] = 1  # N에서 N으로 가는 방법은 1가지 뿐이므로 1을 넣어줌

while queue:
    x = queue.popleft()
    if x == K:
        print(dist[K])
        print(count[K])  # K로 가는 count 역시 함께 출력
        break
    for nx in (x-1, x+1, 2*x):
        if 0 <= nx <= MAX:
            if not dist[nx]:
                dist[nx] = dist[x] + 1
                queue.append(nx)
                count[nx] += count[x]  # nx로 가는 방법의 수에, x까지의 방법의 수를 더해줌
            elif dist[nx] == dist[x] + 1:  # 같은 위치를 최단 시간으로 재방문할 경우도 처리해줌
                count[nx] += count[x]

• count 배열은 특정 지점으로 최단시간 안에 가는 방법의 수를 세는 배열이다.

• 시작점에 해당하는 N에서 N으로 가는 최단시간은 0이며, 그 방법의 수는 1가지 뿐이므로 count[N]에 1을 넣어준다.

• nx라는 지점을 방문할 때, x까지로 최단시간 안에 가는 방법의 수를 더해준다. 이렇게 함으로써 nx까지로 가는 최단경로가 여러개일 때, 방법의 수를 더해나갈 수 있다.

• 만약 한번도 방문하지 않은 곳에서만 위의 처리를 해준다면 최단경로가 여러개인 경우를 고려할 수 없으므로, 같은 위치를 최단 시간으로 재방문할 경우에도 똑같이 처리해준다.

2. 백준 13913번: 숨바꼭질 4

• 추가된 조건: 가장 빠른 시간으로 수빈이가 동생을 찾는 경로를 출력한다. (방법이 여러 개인 경우 뭐를 출력하든 상관 없음)

✔ 숨바꼭질 4 정답 코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
MAX = 10 ** 5
dist = [0] * (MAX+1)
beforeDict = {}  # 이전 지점을 추적할 수 있도록 딕셔너리 정의

queue = deque([N])
while queue:
    x = queue.popleft()
    if x == K:
        print(dist[x])
        break
    for nx in (x-1, x+1, 2*x):  # 0에서 2*0(0)으로 갈때 시간 올라가는거 주의
        if 0 <= nx <= MAX and not dist[nx]:
            dist[nx] = dist[x] + 1
            beforeDict[nx] = x  # A에서 B로 간다면, B라는 key값에 A라는 value가 대응되도록
            queue.append(nx)

# 아래 코드는 queue를 활용해 경로를 역추적 하는 과정
path = [K]
x = K
while x != N:
    x = beforeDict[x]
    path.append(x)
while path:
    print("{}".format(path.pop()), end=" ")
print()

• 딕셔너리를 활용해 이전 지점을 추적할 수 있도록 하였다. 예를 들어 A 지점에서 B로 간다고 가정할 때, B라는 key 값에 A라는 value가 대응되도록 저장하였다.

• 위처럼 저장하면, 끝 지점인 K부터 시작해 시작점 N까지의 경로를 역추적할 수 있다. 이때, queue를 활용해 다시 경로를 시작점부터 출력하도록 한다.

• 한가지 굉장히 헤맸던 부분이 있는데, 위의 코드에서는 x-1, x+1, 2*x 순으로 지점들을 고려했지만, 만약 2배로 가는 경우를 먼저 고려한다면, '틀렸습니다'를 받게 되었다.

• 그 이유는 시작 지점이 0인 경우, 0에서 2배인 지점인 0으로 갈 때, 실제로는 하나도 이동하지 않지만 소요 시간이 1 올라가기 때문이다. 따라서, N=0 K=4와 같은 예시에서 오답이 도출된다.

• 반면, 2배로 가는 지점을 나중에 고려한다면, '맞았습니다'를 받을 수 있었다. 그 이유는 0에서 0으로 갔다가 다른 지점으로 가는 바람에 소요 시간이 1 올라가는 경우보다, 바로 다른 지점으로 가는 경우가 먼저 고려됐기 때문이다. 이미 방문한 곳은 다시 방문하지 않으므로, 잘못 계산된 경우는 자동으로 묻히게 된다.

2배로 갔다가 내려오는 경우가 더 빠를 수도 있어서, MAX 값을 2배 더 크게 잡으라는 말도 있었는데, 그럴 필요는 없었다. 왜냐하면 빼고 2배를 해주면 결국 똑같기 때문이다.