[백준 15558번] 파이썬 - 점프 게임

백준 15558 - 점프 게임

시간 제한 2초, 메모리 제한 512MB

# 조건

• 상근이는 오른쪽 그림과 같은 지도에서 진행하는 게임을 만들었다.
• 지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다.
• 칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.
• 가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.
  • 한 칸 앞으로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.
  • 한 칸 뒤로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.
  • 반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한다. 예를 들어, 현재 있는 칸이 왼쪽 줄의 i번 칸이면, 오른쪽 줄의 i+k번 칸으로 이동해야 한다.
• N번 칸보다 더 큰 칸으로 이동하는 경우에는 게임을 클리어한 것이다.
• 게임을 재밌게 하기 위해서, 상근이는 1초에 한 칸씩 각 줄의 첫 칸이 사라지는 기능을 만들었다.
  • 즉, 게임을 시작한지 1초가 지나면 1번 칸이 사라지고, 2초가 지나면 2번 칸이 사라진다.
  • 편의상 유저가 먼저 움직이고, 칸이 사라진다고 가정한다.
  • 즉, 이번에 없어질 칸이 3번 칸인데, 상근이가 3번 칸에 있다면, 3번 칸에서 다른 칸으로 이동하고 나서 3번 칸이 없어지는 것이다.
• 각 칸의 정보가 주어졌을 때, 게임을 클리어 할 수 있는지, 없는지 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000)
• 둘째 줄에는 왼쪽 줄의 정보가 주어진다.
• i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다.
• 셋째 줄에는 오른쪽 줄의 정보가 주어지고, 각 문자의 의미는 왼쪽 줄의 의미와 동일하다.
• 왼쪽 줄의 1번 칸은 항상 안전한 칸이다.

출력

• 게임을 클리어할 수 있으면 1을, 없으면 0을 출력한다.

# 접근 방법

• bfs를 이용해서 풀어주었다.
• left, right를 따로 관리하기 힘들어서 left를 0번, right를 1번으로 하여 arr과 visited 배열을 생성해준다.
• [+1, -1, +K] 즉 이동할 방법을 di 리스트에 담아준 후 bfs를 돌려주면 된다.
• 이 때, next_idx가 N 이상이면 True를 리턴하고, t초 보다 작거나 같으면 continue를 해주면 된다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import deque

def bfs():
    q = deque()
    q.append((0, 0, 0))
    di = [1, -1, K]
    while q:
        idx, dir, t = q.popleft()
        for d in range(3):
            next_idx = idx + di[d]
            if next_idx >= N: return True
            if next_idx <= t: continue

            if arr[dir][next_idx] == 1 and d != 2 and visited[dir][next_idx] == False:
                q.append((next_idx, dir, t+1))
                visited[dir][next_idx] = True

            elif d == 2 and arr[1-dir][next_idx] == 1 and visited[1-dir][next_idx] == False:
                q.append((next_idx, 1-dir, t+1))
                visited[1-dir][next_idx] = True

    return False


N, K = map(int, input().split())
left = list(map(int, input().strip()))
right = list(map(int, input().strip()))
visited = [[False for _ in range(N)] for _ in range(2)]
arr = [left, right]
visited[0][0] = True

print(1 if bfs() == True else 0)