[BOJ] 15558 - 점프 게임 (Python, JavaScript)

 

 

아이디어

 

BFS로 칸을 이동하며 게임을 클리어할 수 있는지 확인한다.

 

 

풀이 #1 (Python)

 

지도 정보를 lines에 입력 받고, 큐 queue에 칸 인덱스, 줄 인덱스, 시간이 모두 0인 튜플을 초기값으로 저장한다.

 

while문에서 queue에 저장된 튜플을 차례로 꺼내 i, j, t에 저장한다.

반대편 줄의 i+k번 칸으로 이동해 게임을 클리어할 수 있다면 결과값 res에 1을 저장하고 break로 while문을 종료한다.

게임을 클리어할 수 없다면 i+k번 이하의 칸(k는 1 이상이므로 최소 i+1번 칸)은 유효하다.

따라서 반대편 줄의 i+k번 칸, i+1번 칸이 안전하면 queue에 추가하고,

i-1번 칸은 안전한 칸이면서 이번 차례에 사라지지 않으면 queue에 추가한다.

queue에 추가하는 칸들은 다시 방문하지 않도록 lines에 0을 저장한다.

 

def solution():
    N, k = map(int, input().split())
    lines = [list(map(int, [*input()])) for _ in range(2)]
    queue = [(0, 0, 0)]
    res = 0
    while queue:
        i, j, t = queue.pop(0)
        if i+k >= N:
            res = 1
            break
        elif lines[1-j][i+k]:
            queue.append((i+k, 1-j, t+1))
            lines[1-j][i+k] = 0
        if lines[j][i+1]:
            queue.append((i+1, j, t+1))
            lines[j][i+1] = 0
        if i-1 > t and lines[j][i-1]:
            queue.append((i-1, j, t+1))
            lines[j][i-1] = 0
    print(res)

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작한다.

 

자바스크립트에서 빈 배열은 참이므로 while문의 조건식을 queue.length로 한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [N, k] = input[0].split(' ').map(Number);
let lines = [];
for (let i=1; i<3; i++) lines.push(input[i].split('').map(Number));
let queue = [[0, 0, 0]];
let res = 0;
while (queue.length) {
    const [i, j, t] = queue.shift();
    if (i+k >= N) {
        res = 1;
        break;
    }
    else if (lines[1-j][i+k]) {
        queue.push([i+k, 1-j, t+1]);
        lines[1-j][i+k] = 0;
    }
    if (lines[j][i+1]) {
        queue.push([i+1, j, t+1]);
        lines[j][i+1] = 0;
    }
    if (i-1 > t && lines[j][i-1]) {
        queue.push([i-1, j, t+1]);
        lines[j][i-1] = 0;
    }
}
console.log(res);