[백준] 12851번: 숨바꼭질 2

📌 알고리즘 정리

---

📃 문제

 

---

✍ 풀이과정

import sys
from collections import deque
MAX = 100001

n, k = map(int, input().split())
queue = deque([n])
dist = [-1]*MAX
dist[n] = 0
cnt=0

while queue:
    i = queue.popleft()

    if i == k:
        cnt+=1

    if i*2 < MAX and dist[i*2] == -1:
        queue.append(i*2)
        dist[i*2] = dist[i]+1
    if i-1>=0 and dist[i-1] == -1:
        queue.append(i-1)
        dist[i-1] = dist[i] + 1
    if i+1< MAX and dist[i+1] == -1:
        queue.append(i + 1)
        dist[i+1] = dist[i] + 1

print(dist[k])
print(cnt)

3번을 먼저 풀어서 3번에서 appendleft를 append로 바꾸고

i==k일 때마다 cnt를 1씩 추가하는 것으로 수정하였다.

 

출력해봤을 때, 최소 시간은 맞지만 방법 수가 틀리게 나왔다.

생각해보니 처음 방문했을 때만 queue에 추가했기 때문에 1만 출력되는 것이었다.

 

import sys
from collections import deque
MAX = 100001

n, k = map(int, input().split())
queue = deque([n])
dist = [-1]*MAX
dist[n] = 0
cnt=0

while queue:
    i = queue.popleft()

    if i == k:
        cnt+=1

    if i*2 < MAX:
        if dist[i*2] == -1 or dist[i*2] == dist[i]+1:
            dist[i*2] = dist[i]+1
            queue.append(i * 2)
    if i-1>=0:
        if dist[i-1] == -1 or dist[i-1] == dist[i]+1:
            dist[i-1] = dist[i]+1
            queue.append(i - 1)
    if i+1< MAX:
        if dist[i+1] == -1 or dist[i+1] == dist[i]+1:
            dist[i+1] = dist[i]+1
            queue.append(i + 1)

print(dist[k])
print(cnt)

반례를 생각해보다가 도무지 모르겠어서 블로그를 참고했다.

좀 거지같은디,,,이러한 경우에도 추가를 해줘야 한다!

---