BOJ 16174 · 점프왕 쩰리 (Large)

알고리즘 분류 : BFS  

(0, 0)부터 출발하여 점프를 하면서 (N-1, N-1) 도착하는 것을 구현하는 문제다. BFS를 통해 맵을 탐색하면서, 밟은 위치에 쓰여있는 숫자만큼 이동하면 된다. 유사한 문제로 BOJ 16173번 '점프왕 쩰리 (Small)'이 있다. N 범위만 더 적은 문제이므로, 같은 코드로 해결할 수 있다.

• (0, 0)를 큐에 넣고 BFS를 시작한다.
• 아래 방향(↓)과 오른쪽 방향(→)으로만 이동할 수 있으므로 구현이 간단하다.
• 현재 위치에 쓰여있는 숫자만큼 이동한다.
• 방문 여부를 체크하면서 마지막 좌표(N-1, N-1)까지 이동할 수 있는지 확인한다.

---

C++ 소스코드

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

struct jump {
    int x, y;
};

int n, a[64][64];
bool check[64][64];
const int dx[] = {1, 0}, dy[] = {0, 1};

void bfs() {
    queue<jump> q;
    q.push({0, 0});
    check[0][0] = true;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        int k = a[x][y];
        if (x == n-1 && y == n-1) {
            printf("HaruHaru\n");
            return;
        }
        for (int i=0; i<2; i++) {
            int nx = x+dx[i]*k, ny = y+dy[i]*k;
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (!check[nx][ny]) {
                q.push({nx, ny});
                check[nx][ny] = true;
            }
        }
    }
    printf("Hing\n");
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    bfs();
    return 0;
} 

---

Python 3 소스코드

from collections import deque

def bfs():
    q = deque()
    q.append((0, 0))
    check[0][0] = True
    while q:
        x, y = q.popleft()
        k = a[x][y]
        if x == n-1 and y == n-1:
            print("HaruHaru")
            return
        for dx, dy in (1,0), (0,1):
            nx, ny = x+dx*k, y+dy*k
            if 0 <= nx < n and 0 <= ny < n and not check[nx][ny]:
                q.append((nx, ny))
                check[nx][ny] = True
    print("Hing")

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

---

참고

• 백준 온라인 저지 : BOJ 16174
• 백준 온라인 저지 : BOJ 16173