[BOJ/C++] 3055 탈출 : BFS

문제

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

풀이

전형적인 BFS 문제인데 이동하는 대상만 있는 게 아니라, 매시간마다 물이 침범해서 각각 BFS를 해줘야한다. 여기까지 파악했지만, water_bfs()를 어느 시점에 해야하는지 몰라서 해맸다.

✨water_bfs() 해준 후, bfs() 진행하고, cnt 값을 비교해주면 됨
(도착점의 상하좌우 중 최소 한 칸이라도 고슴도치 방문 시간 < 물이면 됨)

⚠️
1. 물의 위치가 여러 개 일 경우 모든 위치를 큐에 넣은 후, 탐색을 시작하는데 기존의 BFS 방식대로 방문 처리를 하면 맨 앞 위치만 방문 처리가 돼서 애초에 큐에 넣을 때 방문 처리를 해줘야 함

2. ans 조건도 BFS 구현 방식대로 했는데 조건이 너무 많아서 알 수 없는 오류가 발생했다. 조건 나눠서 continue 해주고, continue 되지않은 조건에 한해 반복문 끝에서 작업을 수행해주면 조금 더 직관적

코드

#include <iostream>
#include <queue>

using namespace std;

int R, C;
int map[50][50];
bool visited[50][50];
int cnt[50][50];
int water_map[50][50];
bool water_visited[50][50];

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

pair<int, int> s;
pair<int, int> d;
queue<pair<int, int>> water;


void water_bfs() {

	while (!water.empty()) {
		int xx = water.front().first;
		int yy = water.front().second;

		water.pop();
		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && nx < R && ny >= 0 && ny < C && map[nx][ny] == 0 && !water_visited[nx][ny]) {
				water.push({ nx, ny });
				water_visited[nx][ny] = true;
				water_map[nx][ny] = water_map[xx][yy] + 1;
			}
		}
	}
}


void bfs(int x, int y) {
	visited[x][y] = true;
	cnt[x][y]++;

	queue<pair<int, int>> q;
	q.push({ x, y });

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && nx < R && ny >= 0 && ny < C && map[nx][ny] == 0 && !visited[nx][ny]) {
				q.push({ nx, ny });
				visited[nx][ny] = true;
				cnt[nx][ny] = cnt[xx][yy] + 1;
			}
		}
	}

}


int main() {

	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			char tmp;
			cin >> tmp;
			if (tmp == 'X')	map[i][j] = 1; //돌
			else if (tmp == '*') { //물
				water_map[i][j] = 1;
				water.push({ i, j });
				water_visited[i][j] = true;
			}
			else if (tmp == 'S')	s = { i, j }; //시작점
			else if (tmp == 'D') { //도착점
				map[i][j] = 1;
				d = { i, j };
			}

		}
	}

	water_bfs();
	bfs(s.first, s.second);

	int ans = 100001;
	for (int i = 0; i < 4; i++) {
		int nx = d.first + dx[i];
		int ny = d.second + dy[i];
		if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; //범위 벗어난 경우
		if (water_map[nx][ny] > 0 && cnt[nx][ny] >= water_map[nx][ny]) continue; //물로 채워진 경우
		if (cnt[nx][ny] == 0) continue; //도달할 수 없는 경우
		ans = min(ans, cnt[nx][ny]);
	}
	if (ans == 100001)
		cout << "KAKTUS";
	else
		cout << ans;

	return 0;
}