[백준/c++] BOJ 16173 - 점프왕 쩰리 (Small)

https://www.acmicpc.net/problem/16173

16173번: 점프왕 쩰리 (Small)

 

문제 설명

NxN 보드 내부에서 움직이는 점프 게임을 하려고 한다.

출발점은 가장 왼쪽, 가장 위의 칸이며, 가장 오른쪽, 가장 아래 칸에 도달하면 승리한다.

이동 가능한 방향은 오른쪽과 아래 뿐이고, 이동할 때는 현재 밟고 있는 칸에 쓰여진 숫자만큼 이동하여야 한다.

이동 중 방향 조절 불가능하며, 끝 점에 도달할 수 있다면 "HaruHaru"를, 도달할 수 없다면 "Hing"을 출력한다.

N (2 <= N <= 3)

칸에 쓰여진 수 M (0 <= M <= 100)

 

해결

이동 방향과 거리가 제한된 bfs문제이다.

오른쪽, 아래쪽으로 현재 밟고 있는 칸에 쓰여진 숫자만큼 이동하며, 범위를 벗어나지 않고 도달할 수 있게 한다.

어떻게 가도 도달할 수 없는 맵이라면 Hing을 출력하고, 도달했다면 HaruHaru 를 출력한다.

 

queue안에 젤리의 좌표를 넣어 주었으며, 경로의 길이가 중요하지 않으므로 따로 저장해 주진 않았다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n;
int board[4][4];
int visited[4][4];
int dx[2] = { 0, 1 }, dy[2] = { 1, 0 };

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

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int dir = 0; dir < 2; dir++) {
			int nx = cur.x + dx[dir] * board[cur.x][cur.y], ny = cur.y + dy[dir] * board[cur.x][cur.y];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == -1) return 1;
			visited[nx][ny] = 1;
			q.push({ nx, ny });
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> board[i][j];
	}

	if (bfs()) cout << "HaruHaru";
	else cout << "Hing";
}