[Algorithm] 13549. 숨바꼭질 3

13549: 숨바꼭질3

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

• 문제 티어 : G5
• 풀이 여부 : Failed → Solved
• 소요 시간 : 29:25

정답 코드

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

N, K = map(int, input().rstrip().split())

def bfs(cur, dest):
  dq = deque([(cur, 0)]) # 노드, 초
  visited = [False] * 1000001
  visited[cur] = True

  while dq:
    x, sec = dq.popleft()
    if x == dest:
      return sec

    for nx in (x-1, x+1, 2*x):
      if 0 <= nx <= 100000 and not visited[nx]:
        visited[nx] = True
        if nx == 2*x:
          dq.appendleft((nx, sec))
        else:
          dq.append((nx, sec+1))
  return -1

print(bfs(N, K))

접근 방식

이 문제 역시 BFS로 풀이하면서 최소 비용을 위해 우선적으로 처리하면 유리한 조건이 있는 문제다.

    for nx in (x-1, x+1, 2*x):
      if 0 <= nx <= 100000 and not visited[nx]:
        visited[nx] = True
        if nx == 2*x:
          dq.appendleft((nx, sec))
        else:
          dq.append((nx, sec+1))

위와 같이 2*x로 0초가 소요되는 값을 우선적으로 덱에서 처리하기 위해 appendleft() 로 넣어줌으로써 최소 시간을 계산할 수 있다.

잘못된 접근 방식(+ 코드)

# 오답 코드
import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
visited = [False] * 1000001

def bfs(cur):
  dq = deque([(cur, 0)]) # 노드, 초
  path = ['-1', '1', '2']
  visited[cur] = True

  while dq:
    x, sec = dq.popleft()
    if x == K:
      return sec

    for i in range(3):
      if i == 0 or i == 1:
        nx = x + int(path[i])
      else:
        nx = x * int(path[i])

        if 0 <= nx < 100001 and not visited[nx]: 
          if i == 2:
            dq.append((nx, sec))
            visited[nx] = True
          else:
            dq.append((nx, sec+1))
            visited[nx] = True
  return -1

print(bfs(N))

최소 시간을 계산하기 위해서는 순간이동(0초 소요)이 우선적으로 실행되어야 하는데, 이에 대한 처리를 해주지 않았고 또 답이 올바르게 출력되지 않았다.

또한 갈 수 있는 방법 (x-1, x+1, 2*x)을 문자열로 다루어 코드 가독성이 좋지 않았다.

배운점 또는 느낀점

• BFS 유형의 문제에서 Queue를 사용한다고 무조건 FIFO만 사용한다는 생각 버리기!
• 조건에 따라 우선적으로 실행되어야 하는 좌표가 있을 수 있음을 꼭 고려하기!