백준 3055_탈출(C++)

 

www.acmicpc.net/problem/3055

3055번: 탈출

[문제 풀이]

시뮬레이션을 통해 문제를 해결했습니다.

 

고슴도치와 물의 좌표를 queue에 저장해 BFS를 통해 문제를 해결했습니다.

문제에 따르면 물이 먼저 퍼지기 때문에 물을 먼저 queue의 크기만큼 퍼뜨려주고, 그 후 고슴도치 queue의 크기만큼 퍼뜨려 주는 식의 방법을 이용하였습니다.

 

while 문의 탈출 조건은 고슴도치가 목적지의 도달했을 때, 혹은 목적지에 갈 수 없을 때입니다.

[코드]

#include<iostream>
#include<string>
#include<queue>
#include<tuple>

using namespace std;

int R, C, result = 987654321;

queue<pair<int, int>> hedgehog;
queue<pair<int, int>> water;

char forest[51][51] ;
int check[51][51] = { 0, };

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

void BFS();

int main() {

	cin>>R>>C;

	for (int i = 0; i < R; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < C; j++) {
			char temp = str.at(j);

			if (temp == 'S') {
				forest[i][j] = 'S';
				hedgehog.push(make_pair(i, j));
				check[i][j] = 1;
			}
			else if ( temp == '*') {
				forest[i][j] = '*';
				check[i][j] = 2;
				water.push(make_pair(i, j));
			}
			else if (temp == 'X') {
				forest[i][j] = 'X';
				check[i][j] = 3;
			}
			else if (temp == 'D') {
				forest[i][j] = 'D';
				check[i][j] = 4;
			}
		}
	}
	
	BFS();

	return 0;


}

void BFS() {

	int count = 0;

	while (!hedgehog.empty()) {

		count++;

		int water_size = water.size();

		while (water_size--) {

			int x = water.front().first;
			int y = water.front().second;

			for (int i = 0; i < 4; i++) {

				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx < 0 || ny < 0 || nx >= R || ny >= C || check[nx][ny] >= 2)
					continue;

				check[nx][ny] = 2;

				water.push(make_pair(nx, ny));

			}

			water.pop();

		}

		int hedgehog_size = hedgehog.size();

		while (hedgehog_size--) {

			int x = hedgehog.front().first;
			int y = hedgehog.front().second;

			for (int i = 0; i < 4; i++) {

				int nx = x + dx[i];
				int ny = y + dy[i];

				if (check[nx][ny] == 4) {
					cout << count << endl;
					return;
				}


				if (nx < 0 || ny < 0 || nx >= R || ny >= C || check[nx][ny] >= 1)
					continue;

				check[nx][ny] = 1;

				hedgehog.push(make_pair(nx, ny));

			}

			hedgehog.pop();

		}
	}

	cout << "KAKTUS" << endl;
	return;

}