[백준/c++] BOJ 5558 - チーズ (Cheese)

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

5558번: チーズ (Cheese)

 

문제 설명

1부터 N까지의 경도를 가진 치즈를 생산하는 치즈공장이 각각 하나 있다.

쥐가 치즈공장을 돌면서 치즈를 먹으려고 한다.

쥐의 첫 번째 체력은 1이고 치즈 한 개를 먹을 때마다 체력이 1배 증가하지만 쥐는 자신의 체력보다 단단한 치즈를 먹을 수는 없다.

쥐가 인접한 칸으로 이동하는 데에는 1분이 걸리지만, 먹는 시간은 무시한다. 

모든 치즈를 다 먹을 때까지 걸리는 최단 시간 (분)을 출력한다.

H, W, N (1 <= H, W, <= 1000, 1 <= N <= 9) { 순서대로 행, 열, 치즈의 개수를 나타낸다. }

 

해결

일본어로 나와 있는 문제이지만 bfs문제들은 다 거기서 거기이기 때문에... 그냥 입출력 예시만 보고 대충 풀었다.

 

그래도 간단히 설명하자면, 쥐는 자신의 체력보다 단단한 치즈는 먹을 수 없으므로 치즈의 경도가 작은 것부터 순서대로 먹어야 한다.

따라서 N이 3이라면 1->2->3 순서대로 치즈 공장에 방문해야 한다는 뜻이다.

 

방문 처리를 해 주는 visited 배열을 3차원으로 구현하여 쥐의 체력에 따른 방문 처리를 해 주었다.

bfs를 도는 queue 안에는 쥐의 좌표 x, y, 이동한 거리, 지금까지 방문한 숫자를 저장하여 지금까지 방문한 숫자 + 1 인 곳에 방문하게 된다면 숫자를 늘려 주는 방식으로 구현했다.

 

쥐가 벽에 가로막혀 모든 치즈 공장을 다 못 도는 경우는 없으므로 신경 쓰지 않아도 된다.

 

코드

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

int n, m, a;
char board[1001][1001];
pair<int, int> start;
int visited[10][1001][1001];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };

int range_over(int nx, int ny) {
	return nx < 0 || ny < 0 || nx >= n || ny >= m;
}

int bfs() {
	queue<pair<pair<int, int>, pair<int,int>>> q; //좌표 x, y, time, 방문한 숫자
	q.push({ start, {0, 0} });
	visited[0][start.x][start.y];

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.x.x + dx[dir], ny = cur.x.y + dy[dir];
			int time = cur.y.x, num = cur.y.y;

			if (range_over(nx, ny)) continue;
			if (board[nx][ny] == 'X') continue;

			if ((board[nx][ny] != num + 1 + '0' || board[nx][ny] == '.') && visited[num][nx][ny]) continue;
			if (board[nx][ny] == num + 1 + '0') {
				if (num + 1 == a) return time + 1;
				q.push({ {nx, ny}, {time + 1, num + 1} });
				visited[num + 1][nx][ny] = 1;
			}

			q.push({ {nx, ny}, {time + 1, num} });
			visited[num][nx][ny] = 1;
		}
	}
	return 0;
}

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

	cin >> n >> m >> a;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'S') start = make_pair(i, j);
		}
	}

	cout << bfs();
}