백준3055 - 탈출

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

3055번: 탈출

조건이 많아서 조금 복잡한 문제였다. bfs를 이용하여 풀었다. 디큐를 이용하여 처음 시작이 물보다 고슴도치가 우선되게 하였다. 먼저 고슴도치를 진행시키고 물을 진행시켰다. 그렇게 되면 고슴도치가 갔던 길이 물로 덮여서 문제에서 원하던 다음번에 물이 도착할 위치를 고슴도치가 못가게 되기 때문이다. 그리고 현재 시간에 도달한 위치와 다음 번에 이동 가능한 위치의 갯수를 담는 공간을 설정하였다. 현재 시간에 도달한 위치의 갯수가 0인 지점이면 도달 시간을 증가시키고 다음 번에 도달 가능한 공간의 갯수로 최신화하여서 bfs를 다시 진행하였다. 

#include <iostream>
#include <deque>
using namespace std;

//고슴도치인지 물인지 구분해주는 좌표를 클래스로 선언
class Point {
public:
	int x, y, z; //x와 y는 위치, z는 물과 고슴도치를 구분해주는 인자
	Point(int x, int y, int z) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

int m, n; //좌표 크기
int Dx, Dy; //비버 위치
int Sx, Sy; //고슴도치 위치
int cnt = 0; //몇 번만에 도달하는지 카운팅하는 변수
int dx[] = { 1,-1,0,0 }; //행 방향 이동
int dy[] = { 0,0,1,-1 }; //열 방향 이동
int area[2] = { 0, 0 }; //0번지는 현재 시간에 이동한 총 공간(여태까지 이동한 모든 공간 아님), 1번지는 현재에서 바로 다음 번째에 이동한 총 공간
char mat[51][51]; //좌표 정보
bool visit[51][51]; //방문 여부
bool found = false; //비버 굴을 찾은 여부
deque<Point> dq; //고슴도치와 물의 위치정보를 담는 변수

void bfs() {
	while (!dq.empty()) {
		//현재 좌표가 고슴도치인지 물인지 구분하여 찾음
		int x = dq.front().x;
		int y = dq.front().y;
		int z = dq.front().z;

		//맨 앞에 원소 빼줌
		dq.pop_front();

		if (area[0] == 0) { //현재 시간에 이동한 공간이 아무것도 없으면
			cnt++; //방문 시간을 늘리고
			area[0] = area[1]; //바로 이전에 이동한 공간의 갯수를 현재로 이동
			area[1] = 0; //다음번에 방문할 공간을 0으로 만듬
		}

		if (x == Dx && y == Dy) { //현재 위치가 비버굴인 경우
			found = true; //찾았다고 표시하는 변수를 true로 바꾸고
			break; //탈출
		}

		if (z == 1) { //현재 위치가 고슴도치인 경우
			area[0]--; //현재 시간에 이동한 공간의 갯수를 하나 줄여준다.
			for (int i = 0; i < 4; i++) { //상하좌우 이동
				int nx = x + dx[i];
				int ny = y + dy[i];

				//이동하려는 위치가 좌표 범위이고 방문하지 않았으며 물도 아니고 돌도 아니면 그 위치를 방문처리하고 위치 정보에 고슴도치로 넣는다.
				//다음번에 이동하려는 공간의 갯수를 증가시킨다.
				if (1 <= nx && nx <= m && 1 <= ny && ny <= n && !visit[nx][ny] && mat[nx][ny] != '*' && mat[nx][ny] != 'X') { 
					if (mat[nx][ny] == 'D') {
						mat[nx][ny] = 'D';
					}
					else {
						mat[nx][ny] = 'S';
					}
					visit[nx][ny] = true;
					dq.push_back(Point(nx, ny, 1));
					area[1]++;
				}
			}
		}
		else { //현재 위치가 물인 경우
			for (int i = 0; i < 4; i++) { //상하좌우 이동
				int nx = x + dx[i];
				int ny = y + dy[i];

				//이동하려는 위치가 좌표 범위이고 방문하지 않았으며 물도 아니고 돌도 아니고 비버 굴도 아니면 그 위치를 위치 정보에 물로 넣는다.
				if (1 <= nx && nx <= m && 1 <= ny && ny <= n && mat[nx][ny] != '*' && mat[nx][ny] != 'X' && mat[nx][ny] != 'D') {
					mat[nx][ny] = '*';
					dq.push_back(Point(nx, ny, 2));
				}
			}
		}
	}
}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> mat[i][j];
			if (mat[i][j] == 'S') { //입력한 곳이 고슴도치인 경우
				dq.push_back(Point(i, j, 1)); //고슴도치로 그 위치를 위치 정보에 넣는다.
				area[0]++; //현재 고슴도치 위치를 현재 방문할 수 있는 공간의 갯수로 생각해 0번지 증가
				visit[i][j] = true; //방문 처리
			}
			else if (mat[i][j] == '*') { //입려한 곳이 물인 경우
				dq.push_front(Point(i, j, 2)); //물로 그 위치를 위치 정보에 넣는다.
			}
			else if (mat[i][j] == 'D') { //입력한 곳이 비버굴인 경우
				//비버 위치로 최신화
				Dx = i; 
				Dy = j;
			}
		}
	}

	bfs();

	if (found) { //비버굴에 도달한 경우
		cout << cnt;
	}
	else { //비버굴에 도달하지 못한 경우 
		cout << "KAKTUS";
	}
}