(c++)백준 3055번: 탈출

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

3055번: 탈출

[풀이]

bfs사용

물을 인접한 칸에 먼저 이동시킨 후에 고슴도치를 움직인다.

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct State {
	int x, y;
	int cnt;//이동 시간
};

struct Water {
	int x, y;
};

int R, C;
char Forest[50][50];
bool visited[50][50];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
int destX, destY;
queue<State>q;
queue<Water>w;

void bfs() {
	while (!q.empty()) {
		//물 먼저 이동
		int wsize = w.size();
		//현재 물의 위치들에 대해 인접한 구역들 물로 채우기
		while (wsize--) {
			int x = w.front().x;
			int y = w.front().y;
			w.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= R || ny < 0 || ny >= C)
					continue;
				if (Forest[nx][ny] == 'D' || Forest[nx][ny] == 'X' || Forest[nx][ny] == '*')
					continue;
				Forest[nx][ny] = '*';
				w.push({ nx,ny });
			}
		}

		int qsize = q.size();
		while (qsize--) {
			int x = q.front().x;
			int y = q.front().y;
			int cnt = q.front().cnt;
			q.pop();

			if (x == destX && y == destY) {
				cout << cnt << '\n';
				return;
			}

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx < 0 || nx >= R || ny < 0 || ny >= C)
					continue;
				if (Forest[nx][ny] == 'X' || Forest[nx][ny] == '*' || visited[nx][ny] == true)
					continue;
				visited[nx][ny] = true;
				q.push({ nx,ny,cnt + 1 });
			}
		}
	}
	cout << "KAKTUS" << '\n';
}

void solution() {
	cin >> R >> C;
	string s;
	for (int i = 0; i < R; i++) {
		cin >> s;
		for (int j = 0; j < C; j++) {
			Forest[i][j] = s[j];
			if (Forest[i][j] == 'D')
				destX = i, destY = j;
			if (Forest[i][j] == 'S') {
				visited[i][j] = true;
				q.push({ i,j,0 });
			}
			if (Forest[i][j] == '*')
				w.push({ i,j });
		}
	}
	bfs();
}

int main() {
	solution();
	return 0;
}