[백준 16173번] 점프왕 쩰리 (Small) (C++)

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

16173번: 점프왕 쩰리 (Small)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int arr[3][3];
bool visited[3][3];
int dx[] = {0, 1}; //이동방향은 오른쪽과 아래뿐
int dy[] = {1, 0};

int bfs()
{
    queue<pii>q;
    q.push({0, 0});
    visited[0][0]=1;

    while(!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();

        if(arr[y][x] == -1) return 1;

        for(int i=0; i<2; i++)
        {
            int ny = y+dy[i]*arr[y][x]; //해당 위치값만큼 이동가능
            int nx = x+dx[i]*arr[y][x];

            if(ny < 0 || nx < 0 || nx >=N || ny >= N) continue;
            if(visited[ny][nx]) continue;
            visited[ny][nx]=1;
            q.push({ny, nx});
        }
    }
    return 0;
}

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 >> arr[i][j];
        }
    }

    int temp = bfs();
    cout << (temp==1 ? "HaruHaru" : "Hing");

    return 0;
}

bfs로 푼 문제이다.

이동방향이 오른쪽과 아래 2방향인 것에 주의해야 한다.

보통 상하좌우 모두 움직이는 경우가 많아서 dx[] = {0, 0, 1, -1} / dy[] = {1, -1, 0 ,0} 이런식으로 4방향을 주는 경우가 많다.

하지만 해당 문제에서는 방향이 2가지이기에 이에 맞춰서 dx[] = {0, 1} / dy[] = {1, 0} 로 선언해줬다.

 

여기서 bfs 탐색하는 내용을 보면 ny, nx 부분이 일반적인 bfs 형식과 다소 다르다.

보통 기존 y에 dy[i] 값을 더하여 탐색해 나가지만 해당 문제에서는 해당 위치에 있는 값만큼 추가적인 이동이 가능하기에 해당 위치값인 arr[y][x] 값을 곱해준다.

이외에는 bfs의 기본적인 틀에서 크게 벗어나지 않는다.