[백준-Python] 숨바꼭질 : 1697번

🥈 Silver1

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

 

 

메모리	실행시간
40316KB	252ms

 

 

✅ 정답풀이

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


# 최단경로 찾기=최단시간 찾기 (bfs)

def bfs(start,target):
    global cur
    queue=deque([start])
    visited[start]=0 #시작점은 이동거리=0

    while queue:
        cur=queue.popleft()

        if cur==target:
            return visited[cur]

        for i in range(3):
            if i<2:
                nx=cur+dx[i]
            else:
                nx=cur*dx[i]
            
            if 0 <= nx <= max(n, m) * 2 and visited[nx] == -1:
                visited[nx]=visited[cur]+1
                queue.append(nx)



n, m = map(int, input().rstrip().split())
visited = [-1] * (max(n, m) * 2 + 1) #두배까지 이동할수 있기 때문
cur = n  # 수빈 현재위치
dx = [1, -1, 2]  
result=bfs(cur, m)
print(result)

 

수빈이는 1초동안 3가지의 경우로 이동할 수 있고, 동생의 위치까지 도달하는 가장 빠른 시간을 구하는 문제인데, 이는 최단거리 구하는 방식을 사용하면된다. 3가지 방향으로 순차적으로 탐색해 나갈것이기 때문에 BFS가 적절한 방법이고, visited 리스트에 이동해온 거리가 아닌 시간을 저장해둔다. 

 

❗️이동시간을 저장하는 visited 리스트의 길이가 오답의 원인이였다. 

max값의 좌표 위치에서 2배를 이동한다면, 이 값이 최대로 이동할 수 있는 x좌표이기 때문에 최소한 이값 까지 포함한 visited 리스트를 생성해줘야 한다. 다른 풀이를 참고해보니 주로 문제조건에서 주어진 N값의 범위를 사용하였다.