이전에 풀었던 백준 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배를 해주면 결국 똑같기 때문이다.
