[백준/파이썬] 17071번 숨바꼭질 5

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

17071번: 숨바꼭질 5

---

문제 & 테스트 케이스

---

문제 해석

1. 수빈이와 동생의 좌표가 주어진다.

2. 수빈이는 동생의 좌표로 이동해야한다.

3. 수빈이의 이동 방법은 -1, +1, *2 총 3가지 이며 모두 1초가 소요된다.

4. 동생은 매초 1, 2, 3만큼 앞으로만 이동한다.

---

코드

from collections import deque

n, k = map(int, input().split())
visit = [[-1, -1] for _ in range(500001)]

def move(idx, now):
    if idx == 0:
        return now + 1
    if idx == 1:
        return now - 1
    return 2 * now

def bfs(now, k):
    q = deque()
    second = 0
    q.append((now, second))
    visit[now][0] = 0
    while q:
        for _ in range(len(q)):
            now, second = q.popleft()
            for idx in range(3):
                next = move(idx, now)
                if not(0 <= next < 500001): continue
                if visit[next][(second + 1) % 2] != -1: continue
                q.append((next, second + 1))
                visit[next][(second + 1) % 2] = second + 1

bfs(n, k)
ans = -1
second = 0

for i in range(500001):
    k += i
    if k > 500000: break
    if visit[k][second % 2] <= second:
        ans = second
        break
    second += 1
print(ans)

---

문제 풀이

이 문제는 동생의 좌표가 매번 바뀌기 때문에 다른 BFS 문제와 다르게 수빈이가 지나간 곳을 다시 지나갈 수 있어야 한다.

따라서 시간초과를 피할 수가 없어 최대한 최적화를 해주어야 했다.

 

처음 생각한 방법으로 같은 시간내에 같은 좌표로 중복으로 이동할 필요가 없다고 생각했다.

따라서 같은 좌표가 두번 q에 들어가지 않도록 구현을 해주었다.

하지만  이 경우만으로 시간 초과를 해결할 수 없었다.

 

위 방법에 더 최적화를 해줄 방법을 생각해 보았다.

떠오른 방법으로 탐색 도중 현재 동생의 위치보다 수빈이가 앞에 존재했을때,

수빈이의 위치를 다시 큐에 넣지 않고 앞뒤로 움직이면 해당 좌표에 계속 존재한다는 사실을 떠올렸다.

즉, 동생이 위치한 시간대에 수빈이가 위치한 시간대가 서로 짝수거나 서로 홀수라면 그 시간대에 수빈이는 해당 좌표에 존재할 수 밖에 없게된다.

visit[2000]에 수빈이가 4초에 도달했다면, 200초 뒤에 동생이 2000 좌표에 도달했다고 가정하자.

그렇다면 visit[2000]에서 +1 , -1을 반복하면 2000좌표에 항상 존재하게 된다.

따라서 동생이 2000좌표에 도달할때까지 수빈이에게 잡히지 않았다면 답은 200이 된다.

이 논리로 계속 구현해갔지만 어딘가 테스트케이스가 자꾸 어긋나서 결국 통과하지 못했다..

 

머리를 비우고 처음부터 생각을 해보았다.

위 논리는 무조건 맞지만 visit 배열을 짝수, 홀수로 나눈다면 더 확실히 구분해 해결할 수 있을거라 생각했다.

또한 bfs큐와 동생의 좌표값을 동시에 증가시키지 않고

visit 배열에 시간대가 홀, 짝일 경우와 수빈이가 이동할 수 있는 좌표를 2차원 배열로 구성해 해당 시간을 모두 미리 BFS로 입력해주고,

k값을 증가시키며 visit 좌표에 홀짝 시간대에 해당 시간보다 더 작은 값이 존재하면 (누나가 그 좌표에 대기하고 있는 경우)

답을 찾아 풀었다.

수빈이의 시작 좌표에 짝수, 홀수 모두 0을 기입해버려 계속 틀려버리는 대참사...

 

(이정도면 숨바꼭질 마스터)