백준 13549 숨바꼭질 3

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

13549번: 숨바꼭질 3

📌 해결순서

이번에 풀 때도 마찬가지로 times 배열을 만들어서 방문 표시와 걸리는 시간의 표시를 같이 묶어서 하려고 했는데 이 문제에서는 그렇게 하면 안된다.

5에서 첫 번째 이동을 예시로 들면 (4, 6, 10) 으로 이동할 수 있는데 4, 6 은 시간이 +1 되기 때문에 상관이 없지만 10은 방문 했음에도 불구하고 +0을 하기 때문에 여전히 방문하지 않은것으로 여겨진다.

계속 이동을 하다가 다른 좌표를 통해서 10을 다시 방문할 수 있게 되고, 이 경우에는 이미 걸리는 최소시간 0 이 아닌 0보다 큰 값으로 바뀌게 된다.

이렇게 풀면 안됨 ❌❌❌❌❌

 

따라서 times, visited 배열을 따로 만들어줘서 풀었다.

추가로 방문하지 않았던 좌표를 방문할 때마다 항상 그 좌표까지 이동하는데 걸리는 최소 시간을 기록해줘야 한다.

이 점에서 그래프 탐색 문제이지만 그리디 문제라고도 볼 수 있다.

 

어떻게 해결할 수 있을까?

순간이동을 해서 도착한 좌표들에게 먼저 다음 3개의 좌표로 이동할 수 있는 우선순위를 부여함으로써 해결할 수 있다.

 

어떤 지점 x 에서 출발하는 극단적인 예시를 하나 들어보자.

que에 추가된 순서대로 다음 탐색을 진행하게 되는데, 

이렇게 하면 21을 통해서 방문한 20이 우선순위를 가지고 19에 도착할때까지 시간은 3을 사용 하게 된다.

만약, 10 -> 20 을 통해서 19를 방문한다면 시간은 1이다

우선순위를 부여하지 않으면, 더 적은 시간을 사용해서 방문할 수 있는 좌표를 다음 그림과 같이 더 많은 시간을 사용하게 된다.

먼저 이동해서 방문 표시를 해줘야한다!!!

따라서, 순간이동을 통해 시간을 +0 해서 이동한 좌표들에게 우선순위를 부여해서 해결 했다.

 

📌 코드 

from collections import deque
import sys

input = sys.stdin.readline


def bfs():
    que = deque()
    que.append(n)
    visited[n] = True

    while que:
        x = que.popleft()

        if x == k:
            print(times[k])
        for nx in (x - 1, x + 1, x * 2):
            if (0 <= nx <= max) and not visited[nx]:
                if nx == x * 2:
                    visited[nx] = True
                    times[nx] = times[x]
                    que.appendleft(nx)
                    continue

                times[nx] = times[x] + 1
                que.append(nx)
                visited[nx] = True


if __name__ == "__main__":
    n, k = map(int, input().split())
    max = 10**5
    times = [0] * (max + 1)
    visited = [False] * (max + 1)

    bfs()