[백준 12851번] 숨바꼭질 2 - python

문제 링크

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

풀이 - 다른 블로그 참고 

-  bfs 풀이

- visited[i] 는 시작 위치에서 i까지 걸리는 시간의 최솟값 

- cnt 는 가장 빠른 시간으로 찾는 방법의 수 

- 이동할 곳이 범위에 속할 때,

방문하지 않았으면 현재 위치까지 걸린 시간 + 1로 갱신 

방문한 곳이면 이동한 곳까지 걸린 시간이 현재 위치까지 걸린 시간에서 1초를 더한 시간보다 크거나 같으면 작은 값으로 갱신 

from collections import deque 

n, k = map(int,input().split())

cnt = 0 
visited = [-1] * 100001
visited[n] = 0 
q = deque()
q.append(n)

while q :
  x = q.popleft()
  if x ==k :
    cnt += 1 
  for i in (x+1, x-1, x*2):
    if 0 <= i <= 100000:
      if visited[i] == -1 or visited[i] >= visited[x] + 1:
        visited[i] = visited[x] + 1
        q.append(i)

print(visited[k])
print(cnt)

+ 2022.04.12 다시 풀이 

처음에 틀렸던 코드는 다음과 같다.

이유는 큐에 삽입할 때 visited[도착 장소]를 True로 바꿔주어서 최소 시간은 구할 수 있지만 방법 수를 모두 구할 수 없었다. 

# 틀린 코드 
from collections import deque 
import sys
input =sys.stdin.readline 

def bfs(n):
    
    q = deque()
    q.append((n,0))
    
    ans = 0
    t = 0
    
    while q :
        x, cnt = q.popleft()
        
        if x == k :
            t = cnt
            ans += 1 
        else :
            if 0 <= x-1 < 100001 and not visited[x-1]:
                q.append((x-1,cnt+1))
                visited[x-1] = True
            if 0 <= x+1 < 100001 and not visited[x+1]:
                q.append((x+1,cnt+1))
                visited[x+1] = True
            if 0 <= x*2 < 100001 and not visited[x*2]:
                q.append((x*2,cnt+1)) 
                visited[x*2] = True
    
    print(t)
    print(ans)

n, k = map(int,input().split())

visited = [False] * 100001
bfs(n)

- 수정된 코드는 다음과 같다. 큐에서 하나 씩 뺄 때 방문 기록을 해주어서 k에 도착하는 모든 경우의 수를 구할 수 있다. 

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

def bfs(n):
    
    q = deque()
    q.append((n,0))
    
    ans = 0
    t = int(1e9)
    
    while q :
        x, cnt = q.popleft()
        # 이 때 방문 기록 
        visited[x] = True
        
        # k에 도착했고 최단 시간이라면 
        if x == k :
            t = min(t, cnt)
            if t == cnt :
                ans += 1 
        # 범위확인 후 방문하지 않았으면 큐에 삽입 
        else :
            if 0 <= x-1 < 100001 and not visited[x-1]:
                q.append((x-1,cnt+1))
            if 0 <= x+1 < 100001 and not visited[x+1]:
                q.append((x+1,cnt+1))
            if 0 <= x*2 < 100001 and not visited[x*2]:
                q.append((x*2,cnt+1)) 
    
    print(t)
    print(ans)

n, k = map(int,input().split())

visited = [False] * 100001
bfs(n)