취미로 코딩하기

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

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

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

주어진 2차원 배열에서 좌상단 첫 칸에서 출발한 뒤, 매 칸에 도달할 때마다 해당 칸에서 도달가능하면서 아직 방문하지 않은 점들을 DFS 또는 BFS로 탐색해나가자.

위의 탐색 결과 우하단 마지막 칸을 방문한 적이 있다면 문제의 답은 HaruHaru, 그렇지 않다면 Hing이 될 것이다.

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

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

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

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";
}