[BFS] 15558번 점프 게임

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

알고리즘

• BFS

풀이

포인트

• 하나의 상태를 나타내는 조건을 그대로 옮기면 메모리 초과가 난다는 점

BFS

처음에 이 문제를 접했을 때 하나의 상태를 나타내는 조건이 여러개인, 전형적인 조금 어려운 BFS문제라고 생각했다.
그 조건은 아래와 같다.

• x,y 좌표
• 몇초가 지났는지

따라서 처음에 3차원 visited 배열을 아래와 같이 정의했다.

visited = [[[-1]*n for _ in range(n)] for _ in range(2)]

이렇게 하니 메모리 초과가 발생했다.

문제의 제한 조건을 잘보면, $1 <= n,k <= 100,000$으로, 매우 큰 것을 알 수 있다. 위에서 만든 visited 배열의 메모리를 분석해보면, 최악의 경우에는 $2 \times 100000 \times 100000 \times 4B = 2 \times 37.25GB$으로 메모리 낭비가 상당히 심한 것을 알 수 있다.
이를 줄이기 위해, 굳이 현재 몇초인지를 상태에 집어넣을 필요가 있는지에 대해 고민하였다. 이 조건을 집어 넣는게 유의미하려면, 방문하려는 장소 (nx,ny)를 이미 이전에 처음으로부터 4초가 지난 후에 방문했는데, 현재 처음으로부터 7초가 지난 상태에서 (nx,ny)을 방문하는지 결정하는데 도움을 줘야한다. 사실 이는, 이미 visited[nx][ny] != -1 이므로 if 조건에서 걸러질 수밖에 없다.

따라서 `visited` 배열을 아래와 같이 정의하여 메모리 초과를 피하였다.

visited = [[-1]*n for _ in range(2)]

그러면 1초에 한칸씩 없어진다는 조건은 소스코드의 어디에 반영해야할까? 매번 검사하는 if 조건문에, ny > t을 추가하였다.

t는 현재 (x,y)에 있을 때 게임이 진행된 시간이다. 따라서 현재 (x,y)에 있을 때 다음에 가야할 곳은 t보다는 커야한다. 왜냐하면 상근이가 이동하고 나면 t번째 칸은 사라질 것이기 때문이다.

한 가지 주의할 점은, 게임이 n번째 칸에 간다고 해서 끝나는게 아니라 n번째 칸을 넘어설 때 끝난다는 것이다. 따라서 게임이 끝날 조건을 따로 체크해줘야 한다.

[Source Code]

from collections import deque
n,k = map(int,input().split())
a = []
for _ in range(2):
    a.append([int(i) for i in input()])
visited = [[-1]*n for _ in range(2)]
q = deque()
visited[0][0] = 0
q.append((0,0,0))
dx = [-1,1,k]
ans = 0
while q:
    x,y,t = q.popleft()
    for i in dx:
        if i == k:
            nx,ny = 1-x,y+k
        else:
            nx,ny = x,y+i
        if 0 <= nx < 2 and 0 <= ny < n and a[nx][ny] == 1 and\
                visited[nx][ny] == -1 and ny > t:
            visited[nx][ny] = visited[x][y] + 1
            q.append((nx,ny,t+1))
        # 상근이가 맵을 넘어서면 게임이 끝난다.
        elif 0 <= nx < 2 and ny >= n:
            ans = 1
print(ans)