[C++] 백준 17391번: 무한부스터

문제 링크

17391번: 무한부스터

문제 요약

맵의 모든 칸에는 부스터가 존재하고, 각 칸에 멈출때마다 부스터를 획득할 수 있다. 각 칸에서 부스터를 획득하면, 가지고 있던 부스터 갯수 이하만큼 오른쪽 또는 아래으로 이동할 수 있다. 단, 한 방향으로 이동하면 다른 방향은 선택할 수 없고, 부스터를 사용하고 멈추면 원래 가지고 있던 부스터는 사라진다.
(N, M)번 칸에 도착하기 위해 부스터를 사용하는 횟수의 최솟값을 구해야 한다.

접근 방법

간단한 BFS 문제입니다.

아래쪽, 그리고 오른쪽 방향으로만 이동하는 BFS를 구현해주면 됩니다.

1부터 현재 소지하고 있는 부스터 갯수까지 for문을 돌려 증가시키며 방향을 가리키는 변수와 곱해서 현재 위치에 더해주고, 재방문 여부나 범위를 체크한 후에 큐에 넣어주면 됩니다.

쉬운 문제였는데, 컨디션이 너무 안 좋아서 문제를 자세히 안 읽었다가 오른쪽과 아래로만 이동 가능하다는 조건을 못 봐서 한 번 틀렸습니다. 문제를 신중히 읽어야 한다는 것을 주기적으로 한 번씩 깨닫게 되는 것 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 301;
int n, m, mp[MAX][MAX], dir[2][2] = { {0, 1}, {1, 0} };
bool visited[MAX][MAX];

struct Data {
	int r, c, d;
};

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> mp[i][j];

	queue<Data> q;
	q.push({ 1, 1, 0 });

	while (!q.empty()) {
		auto now = q.front();
		q.pop();

		if (now.r == n && now.c == m) {
			cout << now.d << '\n';
			return 0;
		}

		int booster = mp[now.r][now.c];

		for (int i = 0; i < 2; i++) {
			for (int j = 1; j <= booster; j++) {
				int nr = now.r + dir[i][0] * j;
				int nc = now.c + dir[i][1] * j;
				
				if (nr >= 1 && nr <= n && nc >= 1 && nc <= m && !visited[nr][nc]) {
					visited[nr][nc] = true;
					q.push({ nr, nc, now.d + 1 });
				}
			}
		}
	}
}