[BOJ 15558] 점프 게임

문제

점프 게임

문제 해설

두개의 리스트가 주어지고 한칸씩 이동불가 지역으로 변하면서 반드시 앞, 뒤 혹은 옆 리스트로 이동해 나가는 게임이다. 이동을 할 수 있다면 좌표와 왼쪽, 오른쪽 리스트인지 판단하는 변수를 큐에 삽입하여 해결했다. 조금 신경써야 하는 것은 두 리스트가 한 칸씩 이동 불가 지역이 되어 가는 것만 신경 쓰면 된다.

처음에 시간초과가 떠서 visited 라는 중복된 인덱스를 처리하는 변수를 만들어 해결했다.

소스 코드

# 4:09
from collections import deque

answer = 0
time = 0
q = deque()
n, k = map(int, input().split())
left = list(map(int, input()))
right = list(map(int, input()))
lvisited = [False] * n
rvisited = [False] * n
q.append(("l", 0))


while q:
    size = len(q)
    for i in range(size):
        direct, idx = q.popleft()
        if idx + k >= n or idx + 1 >= n:  # 클리어 가능
            q.clear()
            answer = 1
            break

        if direct == "l" and not lvisited[idx]:  # 왼쪽 리스트에 존재
            if left[idx + 1] == 1:  # 앞으로 한칸 이동 가능
                q.append(("l", idx + 1))

            if idx - 1 >= 0 and idx - 1 > time and left[idx - 1] == 1:  # 뒤로 한칸
                q.append(("l", idx - 1))
            if right[idx + k] == 1:  # 오른쪽리스트로 이동
                q.append(("r", idx + k))

        if direct == "r" and not rvisited[idx]:  # 오른쪽 리스트
            if right[idx + 1] == 1:  # 앞으로 한칸 이동 가능
                q.append(("r", idx + 1))
            if idx - 1 >= 0 and idx - 1 > time and right[idx - 1] == 1:  # 뒤로 한칸
                q.append(("r", idx - 1))
            if left[idx + k] == 1:  # 왼쪽으로 이동
                q.append(("l", idx + k))
        if direct == "l":
            lvisited[idx] = True
        else:
            rvisited[idx] = True
    left[time] = 0
    right[time] = 0
    time += 1
print(answer)