문제 출처

1. 문제설명

  • 어떤 지도가 주어진다.
  • 지도는 R행 C열로 이루어져 있다.
  • 비어있는 곳은 ‘.’, 물이 차있는 지역은 ‘*’, 돌은 ‘X’, 비버의 굴은 ‘D’, 고슴도치의 위치는 ‘S’
  • 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽)
    • 물도 비어있는 칸으로 확장한다.

  • 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하라

  • 문제 분류
    • Graph, BFS


2. 알고리즘 설계

  • 전형적인 BFS 문제에서 물이 확장되는 조건이 추가된 문제이다.
  • 본인은 2차원 배열을 사용해 물이 차오를 수 있는 지역의 시간을 체크해주었다.
  • 만약 시간 내에 지나갈 수 있으면 패스, 아니라면 못 가는 걸로


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 52;
int n, m, start_i, start_j, end_i, end_j;
char a[SIZE][SIZE];
int water_day[SIZE][SIZE];
int check[SIZE][SIZE];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { -1, 1, 0, 0 };

queue<pair<int, int>> water;

void water_bfs() {
	while (!water.empty()) {
		int x = water.front().first;
		int y = water.front().second;
		water.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (water_day[nx][ny] == 0 && a[nx][ny] == '.') {
					water_day[nx][ny] = water_day[x][y] + 1;
					water.push(make_pair(nx, ny));
				}
			}
		}
	}
}

void bfs() {
	queue<pair<int, int>> q;
	q.push(make_pair(start_i, start_j));
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (check[nx][ny] == 0 && (a[nx][ny] == '.' || a[nx][ny] == 'D')) {
					if (water_day[nx][ny] == 0) {
						check[nx][ny] = check[x][y] + 1;
						q.push(make_pair(nx, ny));
					}
					else {
						if (water_day[nx][ny] > check[x][y] + 1) {
							check[nx][ny] = check[x][y] + 1;
							q.push(make_pair(nx, ny));
						}
					}
				}
			}
		}
	}
}

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

    cin >> n >> m;

	for (int i = 0; i < n; i++) {
        cin >> a[i];
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'S') {
				start_i = i;
				start_j = j;
			}
			else if (a[i][j] == 'D') {
				end_i = i;
				end_j = j;
			}
			else if (a[i][j] == '*') {
				water.push(make_pair(i, j));
			}
		}
	}

	water_bfs();
	bfs();

	if (check[end_i][end_j] != 0)
		cout << check[end_i][end_j];
	else 
		printf("KAKTUS\n");
}