BOJ 15558 · 점프 게임

알고리즘 분류 : BFS  

점프 이동을 하면서 타일을 벗어나는 게임을 구현해야 한다. 점프 이동은 3가지이며, 한 번에 하나씩 진행하므로 BFS 탐색을 통해 해결할 수 있다.

• 맵 좌표의 인덱스는 [왼쪽 또는 오른쪽 줄] [줄 번호] 이다. 왼쪽 줄은 0이고, 오른쪽 줄은 1이다.
• 현재 좌표를 (X, Y)라 했을 때, 다음 좌표는 아래 3가지로 나타낼 수 있다.
• 한 칸 앞으로 이동 : (X, Y+1)
• 한 칸 뒤로 이동 : (X, Y-1)
• 반대편 줄 점프 : (!X, Y+K)
• 매초마다 타일이 한 칸씩 없어지는 것을 고려해야 한다.
• 타일을 완전히 벗어나면, 즉 Y 인덱스가 N 이상이면 게임을 클리어 한 것이다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

int n, k;
char a[2][100001];
bool check[2][100001];

void bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});
    for (int i=0; i<n; i++) {
        for (int j=0; j<(int)q.size(); j++) {
            int x = q.front().first, y = q.front().second; q.pop();
            int nx[] = {x, x, !x}, ny[] = {y-1, y+1, y+k};
            for (int k=0; k<3; k++) {
                if (ny[k] >= n) {
                    printf("1\n");
                    return;
                }
                if (ny[k] <= i || check[nx[k]][ny[k]] || a[nx[k]][ny[k]] == '0') continue;
                q.push(make_pair(nx[k], ny[k]));
                check[nx[k]][ny[k]] = true;
            }
        }
    }
    printf("0\n");
}

int main() {
    scanf("%d %d", &n, &k);
    scanf("%s %s", a[0], a[1]);
    bfs();
    return 0;
}

---

Python 3 소스코드

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

def bfs():
    q = deque()
    q.append((0, 0))
    for i in range(n):
        for j in range(len(q)):
            x, y = q.popleft()
            for nx, ny in (x, y-1), (x, y+1), (not x, y+k):
                if ny >= n:
                    print(1)
                    return
                if ny > i and not check[nx][ny] and a[nx][ny] == '1':
                    q.append((nx, ny))
                    check[nx][ny] = True
    print(0)

n, k = map(int, input().split())
a = [list(input().strip()) for _ in range(2)]
check = [[False]*n for _ in range(2)]
bfs()

---

참고

• 백준 온라인 저지 : BOJ 15558