1. 문제 분석하기

1.1. 문제 의도

• 이번 문제의 유형은 시뮬레이션 및 구현입니다.
• 문제를 읽고 복잡한 조건을 잘 정리한 뒤 빠짐없이 구현하는 능력이 필요합니다.

1.2. 문제 조건

1. 물이 고슴도치보다 먼저 이동해야합니다.
2. 물은 돌과 소굴을 지나갈 수 없습니다.
3. 고슴도치는 돌과 물을 지나갈 수 없습니다.
4. 처음에 물은 여러 개 있을 수 있습니다!!!

2. 문제 해결하기

• 출발지와 목적지가 정해져있고, 최적해를 구하므로 BFS를 사용합니다.
• 물도 이동하고 고슴도치도 이동하므로 queue를 2개 사용합니다.
• 고슴도치는 물이 찰 예정인 칸을 지나갈 수 없으므로 물이 먼저 이동합니다.
• 1분 당 물 queue에 들어있는 요소들에 대해 이동을 진행,
  고슴도치 queue에 들어있는 요소들에 대해 이동을 진행,
  목적지에 도달했다면 끝, 그렇지 않다면 1분 추가하는 과정을 반복합니다.

Tip: 의외로 범위 검사하는 코드가 횟수가 많아지면 꽤 큰 overhead가 됩니다. 이런 경우 저는 양사이드에 한 칸 씩을 더 만든 뒤 사용합니다. 이게 더 효율적이고 빠르더라구요.

3. 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

int d[4][2] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
int R, C, goalY, goalX;
bool visited[52][52];
char map[52][52];
queue<pair<int, int>> qWater, qMole;

int simulate() {
	int tick = 0;
	while (!qMole.empty()) {
		// 먼저 현재 phase에서 물이 있는 칸을 이동시킨다.
		int numWater = qWater.size();
		while (numWater--) {
			int cy = qWater.front().first, cx = qWater.front().second;
			qWater.pop();
			for (int i = 0; i < 4; ++i) {
				int ny = cy + d[i][0], nx = cx + d[i][1];
				// 물은 돌과 목적지를 지나갈 수 없다.
				if (map[ny][nx] == '.') {
					map[ny][nx] = '*';
					qWater.push({ny, nx});
				}
			}
		}
		// 그 뒤 현재 phase에서 고슴도치가 있을 수 있는 칸을 이동시킨다.
		int numMole = qMole.size();
		while (numMole--) {
			int cy = qMole.front().first, cx = qMole.front().second;
			qMole.pop();
			visited[cy][cx] = true;
			if (cy == goalY && cx == goalX) return tick;
			
			for (int i = 0; i < 4; ++i) {
				int ny = cy + d[i][0], nx = cx + d[i][1];
				// 고슴도치는 물과 돌을 지나갈 수 없다.
				if (map[ny][nx] != 'X' && map[ny][nx] != '*'&& !visited[ny][nx]) {
					visited[ny][nx] = true;
					qMole.push({ny, nx});
				}
			}
		}
        tick++;
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> R >> C;
	memset(map, 'X', sizeof(map));
	
	for (int y = 1; y <= R; ++y)
		for (int x = 1; x <= C; ++x) {
			cin >> map[y][x];
			if (map[y][x] == 'D') goalY = y, goalX = x;
			else if (map[y][x] == 'S') qMole.push({y, x});
			else if (map[y][x] == '*') qWater.push({y, x});
		}
	int answer = simulate();
	if (answer == -1) cout << "KAKTUS";
	else cout << answer;
}

4. 결과