점프게임

파이프 옮기기1을 풀다가 도저히 오늘 안에는 풀지 못할것 같아서 다른 문제를 풀었다.

점프 게임은 기본 BFS 문제에서 몇 가지를 조금 더 생각해서 풀어야 하는 문제이다.

할 수 있는 행동은 아래와 같다.

  • 같은 줄의 한 칸 앞으로 이동한다.
  • 같은 줄의 한 칸 뒤로 이동한다.
  • 반대편 줄의 k칸 앞으로 이동한다.

1초에 한 번씩 세개의 행동들 중 하나를 하게 되고, 상근이가 움직인 후에 1초에 한 번씩 첫 줄 부터 한 칸씩 사라진다.

이때, 상근이가 N보다 더 큰 수의 칸으로 이동하게 되면 게임을 클리어 한 것이다.

지도와 동일한 크기의 check 배열을 만들어 방문여부를 체크하며 BFS를 진행했다.

또한, 1초에 한 칸씩 사라지는 칸들을 탐지하기 위해 BFS한 사이클을 돌 때 마다 disappear 변수를 1씩 증가시키고, 상근이의 위치가 disappear 보다 작을 때는 해당 점의 BFS 탐색을 진행하지 않았다.

게임을 클리어 하는 조건은 아래와 같다.

if b>=n-1 or b+k>=n:
    print(1)
    sys.exit()

현재 칸에 k를 더한 값이 n이상일 때, 혹은 b가 n-1보다 크거나 같으면 게임을 클리어했다고 볼 수 있다. b가 n-1이면, 바로 한 칸 앞으로 이동해 n으로 갈 수 있고 지도는 n-1까지만 존재하고 지도 넘어의 칸으로는 항상 이동할 수 있기 때문에 b과 n-1이 같을 때도 게임을 클리어했다고 할 수 있는 것이다.

  • 반대편 줄의 k칸 앞으로 이동하는 경우 상근이가 왼쪽 줄에 위치해 있는지, 오른쪽 줄에 위치해 있는지에 따라서 각각 코드를 작성해 주었다.
  • 뒤로 한 칸 이동할 때는 0보다 클 때만 이동할 수 있도록 해주었다.
  • check 리스트를 활용해 이미 방문했던 위치인지 확인하고, 방문하지 않은 곳들에 대해서만 탐색해 나갔다.


CODE

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

n,k=map(int,read().split())

MAP=list(list(map(int,read().strip())) for _ in range(2))
#방문 여부 체크
check=list(list(True for _ in range(n)) for _ in range(2))

point=deque([[0,0]])
check[0][0]=False

#사라진 칸인지 확인하기 위한 변수
disappear=-1

while point:
    disappear+=1
    for _ in range(len(point)):
        a,b=point.popleft()
        #이미 사라진 칸이라면, BFS를 진행하지 않는다.
        if disappear>b:continue
        #b가 N번 이상의 칸에 도달하면 게임이 클리어된다.
        if b>=n-1 or b+k>=n:
            print(1)
            sys.exit()
        #한칸 앞으로 이동
        if MAP[a][b+1] == 1 and check[a][b+1]:
            point.append([a,b+1])
            check[a][b+1]=False
        #한칸 뒤로 이동
        if b-1>=0 and MAP[a][b-1] == 1 and check[a][b-1]:
            point.append([a,b-1])
            check[a][b-1]=False
        #현재 아래칸에 있는 경우
        if a==1:
            if b+k<n and MAP[0][b+k]==1 and check[0][b+k]:
                point.append([0,b+k])
                check[0][b+k]=False
        #현재 윗칸에 있는 경우
        if a==0:
            if b+k<n and MAP[1][b+k]==1 and check[1][b+k]:
                point.append([1,b+k])
                check[1][b+k]=False
#BFS 탐색을 마치고도 코드가 종료되지 않은 경우,
#게임을 클리어하지 못했다는 의미이다.    
print(0)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]