[BOJ 16173 // C++] 점프왕 쩰리 (Small)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16173번 문제인 점프왕 쩰리 (Small)이다.
문제는 아래 링크를 확인하자.

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

16173번: 점프왕 쩰리 (Small)

16174번 문제에서 입력이 작아진 문제이다.

 

이 문제의 경우 직접 가능한 경로의 경우의 수를 각 칸의 나열의 순열(permutation)을 이용해 탐색해 볼 수도 있겠지만 그 구현보다는 DFS 또는 BFS 등의 그래프 탐색 구현이 더 간단하므로 16174번 문제의 풀이를 참고해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N;
int board[3][3];
bool visited[3][3];

void bfs() {
	visited[0][0] = 1;
	queue<pair<int, int>> que;
	que.push(make_pair(0, 0));
	
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		int d = board[r][c];
		if (0 <= r - d && !visited[r - d][c]) {
			visited[r - d][c] = 1;
			que.push(make_pair(r - d, c));
		}
		if (r + d < N && !visited[r + d][c]) {
			visited[r + d][c] = 1;
			que.push(make_pair(r + d, c));
		}
		if (0 <= c - d && !visited[r][c - d]) {
			visited[r][c - d] = 1;
			que.push(make_pair(r, c - d));
		}
		if (c + d < N && !visited[r][c + d]) {
			visited[r][c + d] = 1;
			que.push(make_pair(r, c + d));
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) cin >> board[r][c];
	}

	bfs();

	if (visited[N - 1][N - 1]) cout << "HaruHaru";
	else cout << "Hing";
}