C++ ) 백준 3055 탈출

 

 

 

문제)

 

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

3055번: 탈출

 

 

BFS가 같은 맵에서 2번 진행되어야 하는 문제다.

 

1. 젖은 물의 공간이 확장되며 (BFS)

2. 고슴도치의 최소 거리를 구해야 한다. (BFS)

 

 

구현 자체는 어렵지 않으나 3가지를 어떻게 해결할 것인지가 관건일 것 같다.

 

1. 고슴도치는 물에 젖게 될 곳에도 가면 안된다.

 

-> 젖은 물의 공간을 먼저 확장하고, 그 다음으로 고슴도치의 BFS를 진행함으로써 해결했다.

 

2. 서로 다른 지점에서의 BFS 두 가지를 진행하는 방법?

 

-> 한 지점에서의 BFS는 while 문을 통해서 queue가 empty가 될 때 까지 진행한다.

하지만 두 가지를 한꺼번에 하기위해서는 queue가 empty가 될 떄 까지 계속 진행되는 것이 아닌(물이 전체적으로 확장되는 것이 아닌), 물이 1번 확장되고 고슴도치가 갈 수 있는 길이 1번 확장되고를 번갈아 해야한다.

 

이 문제를 해결하기 위해서는 각각의 확장을 진행하기 전에 queue의 size를 구해서,

물이 1번 확장이 되고 queue에 담긴 나머지는 다음에 확장이 되도록 (고슴도치가 1번 확장이 된 후에) 큐에 남겨놓는 방법이다.

즉, bfs 전에 queue의 길이를 구해서 bfs가 한 칸씩만 확장되도록 한다.

 

3. 1번씩 확장하는 것을 반복할 때 탈출 조건

 

-> 고슴도치가 무사히 목적지에 도착했으면 값을 'W(in)'으로 바꾸도록 설정했다.

탈출 조건은 목적지가 D에서 W로 바뀌었거나, 고슴도치가 더 이상 갈 곳이 없을 때(Move.empty()) 탈출문을 나오도록 설정했다.

 

#include <iostream>
#include <queue>

using namespace std;

char map[50][50];
int Fcheckmap[50][50]; // 물의 방문 체크
int Mcheckmap[50][50]; // 고슴도치의 방문 체크

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

int R, C;
int yy, xx; // D(목적지)의 y좌표, x좌표를 담을 곳
int Count = 0;


void Solve(queue <pair<int, int>> & Move , queue <pair<int, int>> & Flood){

	int Movesize;
	int Floodsize;
	int tmpy;
	int tmpx;
	pair<int, int> tmp;

	//cout << "flood" << endl;
	while (map[yy][xx] != 'W' && !Move.empty()) {

		//cout << "count is " << Count << endl;

		Movesize = Move.size(); // 미리 queue의 길이를 세어 길이 1만큼만 확장하도록
		Floodsize = Flood.size(); //미리 queue의 길이를 세어 길이 1만큼만 물에 젖도록

		while (!Flood.empty() && Floodsize)
		{
			Floodsize--;
			tmp = Flood.front();
			Flood.pop();
			for(int i = 0; i < 4; i++)
			{
				tmpy = tmp.first + dy[i];
				tmpx = tmp.second + dx[i];

				if (tmpy < 0 || tmpy >= R || tmpx < 0 || tmpx >= C || map[tmpy][tmpx] == 'X' || Fcheckmap[tmpy][tmpx] || map[tmpy][tmpx] == 'D')
					continue; // 맵을 넘어가거나, 돌을 만나거나, 이미 방문했거나, 목적지라면 진행하지 않는다.
//				cout << tmpy << " " << tmpx << endl;
				map[tmpy][tmpx] = '*'; // 물에 젖음을 미리 표시 (여기에는 가지 않게)
				Flood.push(make_pair(tmpy, tmpx)); // queue에 넣어준다.
				Fcheckmap[tmpy][tmpx] = 1; // 방문 표시한다.
			}
		}

		//cout << "move" << endl;
		while (!Move.empty() && Movesize)
		{
			Movesize--;
			tmp = Move.front();
			Move.pop();
			for(int i = 0; i < 4; i++)
			{
				tmpy = tmp.first + dy[i];
				tmpx = tmp.second + dx[i];

				if (tmpy < 0 || tmpy >= R || tmpx < 0 || tmpx >= C || map[tmpy][tmpx] == 'X' || map[tmpy][tmpx] == '*' || Mcheckmap[tmpy][tmpx])
					continue; // 맵을 넘어가거나, 돌을 만나거나, 물이 있거나, 이미 방문했다면 진행하지 않는다.

				//cout << tmpy << " " << tmpx << endl;

				if (map[tmpy][tmpx] == 'D')
					map[tmpy][tmpx] = 'W'; // 목적지에 도착했다면 'W'로 바꿔주어 탈출 조건을 만들어준다.
				Move.push(make_pair(tmpy, tmpx));
				Mcheckmap[tmpy][tmpx] = 1;
			}
		}
		Count++; // 몇 번 만에 목적지에 도착했는지 센다.
	}

	if (map[yy][xx] == 'W')
		cout << Count;
	else
		cout << "KAKTUS";

}
int main() {

	cin >> R >> C;

	queue <pair<int, int>> Move;
	queue <pair<int, int>> Flood;

	char tmp;


	for(int i = 0; i <R; i++)
	{
		for(int j = 0; j < C; j++)
		{

			cin >> tmp;
			if (tmp == 'S') {
				Move.push(make_pair(i, j)); // 고슴도치 좌표 queue에 넣기
				Mcheckmap[i][j] = 1;
			}
			if (tmp == '*') {
				Flood.push(make_pair(i, j)); // 젖은 지역 queue에 넣기
				Fcheckmap[i][j] = 1;
			}
			if (tmp == 'D')
			{
				yy = i;
				xx = j;
			}
			map[i][j] = tmp;
		}
	}

	Solve(Move, Flood);
}