[BOJ_16174_RN] 점프왕 쩰리 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/16174

문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ), BFS ( Breadth First Search ) 알고리즘

해설

쩰리가 움직이기 시작하는 위치인 (0, 0) 부터 queue에 넣어 순차적으로 탐색을 시작한다. 쩰리는 오른쪽 또는 아래쪽만 이동이 가능하기 때문에 선택가능한 선택지는 두가지이하다. 맵 밖을 나가지 않으면서 이미 방문했던 칸이 아닌 곳을 계속 queue 에 넣어주며 (N - 1, N - 1)을 도달할 수 있는지 확인하면 된다. (N - 1, N - 1)좌표로 이동했다면 승리, 이동하지 못했다면 패배가 된다.

정당성 증명

이미 방문한 칸을 다시 탐색하지 않아도 되는 이유는 결과가 중복되기 때문이다. 칸에 쓰여져 있는 수가 변하지 않기 때문에 몇번을 탐색하여도 같은 결과가 나오게 된다. 그래서 이미 지나간 칸이라면 연산이 중복되기 때문에 다시 탐색할 필요가 없다.

시간복잡도

V : 노드

E : 간선

이 코드의 시간복잡도는 queue에 들어갈 원소의 갯수 ( 노드의 갯수 ) 와 간선의 갯수이다. 일반적으로 BFS로 짜여진 코드는 간선이 리스트로 짜여진 BFS는  이고 간선이 행렬로 구현된 BFS는  이다 이 코드는 간선의 갯수가  개로 고정되어 있으므로 이 코드의 시간복잡도는  즉  가 된다.

점프왕 쩰리 코드 [ C++ ]

#include <cstdio>
#include <queue>
int ar[65][65];
int mem[65][65];
int dirX[2] = { 1, 0 };
int dirY[2] = { 0, 1 };
int main() {
    int n, f = 0;
    std::queue < int > q;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", ar[i] + j);
        }
    }
    q.push(0);
    q.push(0);
    for (; !q.empty(); ) {
        int x = q.front(); q.pop();
        int y = q.front(); q.pop();

        if (x == n - 1 && y == n - 1) {
            f = 1;
            break;
        }

        for (int i = 2; i--; ) {
            int xx = dirX[i] * ar[x][y] + x, yy = dirY[i] * ar[x][y] + y;
            if (xx >= n || yy >= n || mem[xx][yy]) continue;
            q.push(xx);
            q.push(yy);
            mem[xx][yy] = 1;
        }
    }
    puts(f ? "HaruHaru" : "Hing");
    return 0;
}