백준16173-점프왕 쩰리 (small)

문제 링크

점프왕 쩰리 small

난이도

🥈실퍼 4
체감난이도는 1260번 문제랑 비슷해서(어려워서X) 4는 의아하다

유의점

한칸씩 이동이 아니라 점프칸에 쓰인 숫자만큼 이동해야한다
칸이 100칸인 게 아니라 칸에 쓰인 정수의 숫자 범위이다

정답 코드

#include<iostream>
#include<queue>
using namespace std;
int map[3][3];
bool visit[3][3];
queue<pair<int, int>>q;
int dx[] = { 0,1 };
int dy[] = { 1,0 };//아래와 왼쪽으로 움직이는 것을 나타내기 위하여
int n;
int bfs(int x, int y) {
	q.push(make_pair(x, y));
	visit[0][0] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		visit[x][y] = true;
		q.pop();
		int step = map[x][y];
		for (int i = 0; i < 2; i++) {
			int nx = x + step * dx[i];
			int ny = y + step * dy[i];
			if (!visit[nx][ny] && nx<n&&ny<n) {
				visit[nx][ny] = true;
				if (map[nx][ny] == -1) {
					return 1;
				}
				q.push(make_pair(nx, ny));
			}
			}
		}
	return 0;
	}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	int ans=bfs(0, 0);
	if (ans) {
		cout << "HaruHaru" << "\n";
	}
	else {
		cout << "Hing" << "\n";
	}
}

문제 푸는법

제일 먼저 떠오른 풀이:dfs나 bfs
일단 solved.ac기준 dp나 브루트포스로 푼 유저도 있음