[백준] 16174번 점프왕 쩰리 (Large)

문제 링크: https://www.acmicpc.net/problem/16174

문제

입출력

문제 접근

그래프 탐색 문제이다.
bfs를 사용해서 문제를 해결했다.
각 자리의 숫자만큼, 오른쪽과 아래쪽으로 갈 수 있는 경로를 체크한 후, 갈 수 있다면, 해당 노드를 넣어주었다. 만약 (N-1, N-1)노드에 도착했다면, true, 도착하지 않았다면 false를 출력해주었다.

코드 구현(c++)

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int N;
int map[64][64];
int check[64][64];
int moveX[2] = {0,1};
int moveY[2] = {1,0};

bool bfs(){
    queue<pair<int,int> > q;
    check[0][0] = true;

    q.push(make_pair(0,0));

    while(!q.empty()){
        int x = q.front().first; int y = q.front().second;
        q.pop();
        if(map[y][x] == -1) return true;
        for(int i = 0 ; i < 2 ; i++){
            int nextX = x + moveX[i]*map[y][x]; int nextY = y + moveY[i]*map[y][x];
            if(nextX >= N || nextY >= N || check[nextY][nextX]) continue;
            check[nextY][nextX] = true;
            q.push(make_pair(nextX,nextY));
            
        }
    }
    return false;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> map[i][j];
        }
    }

    memset(check, false, sizeof(check));
    if(bfs()) cout << "HaruHaru\n";
    else cout << "Hing\n";
}