[BOJ 백준] 탈출(3055) C++

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

3055번: 탈출

 

문제 설명 : 

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

 

입력 : 

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

 

출력 : 

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

 

예제 입력 : 

5 4 .D.* .... ..X. S.*. ....

 

예제 출력 : 

4

 

접근법 : 

1) 어떻게 풀 것인가?

지도가 주어지고 홍수가 발생함에 따라 장애물을 피해 목적지로 간다.

 

→ Flood fill을 통해 완전탐색이 가장 기본적으로 떠오른다.

     시간 복잡도를 확인해봐야겠지만 이러한 문제 유형은 정말 까다로운 DP 점화식을 세우는 문제가 아닌 이상

    BFS 완전탐색으로 충분히 해결 가능하다. 단, 난이도가 상승할수록 장애물 조건은 까다로워질 수 있다.

 

BFS, DFS 모두 가능하지만 백트래킹이 복잡하므로 (고슴도치와 물 2가지 종류가 존재) BFS를 추천

 

참고자료 : 플러드 필 알고리즘 wiki https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

플러드 필 - 위키백과, 우리 모두의 백과사전

2) 시간복잡도

R과 C가 최대 50이므로 최악의 경우 2,500으로 아주 넉넉하다.

(C++ 실행시간 0ms)

 

3) 공간복잡도

지도는 char, int 모두 가능. 넉넉하게 int로 해도 4Bytes * 50 * 50 = 약 9.76Kbytes로 넉넉하며

Queue를 아무리 넉넉잡고 5,000개 잡아도 굳이 계산 안 해도 될정도로 여유있다.

 

 

4) 풀면서 놓쳤던점

- 물이 먼저 차오르고, 고슴도치가 나중에 이동한다는 조건은 Queue를 1개만 사용해도 된다는 배려의 조건이었는데

  굳이 Queue를 2개로 사용했다. → 가독성 자체는 Queue 2개 사용하는 것이 더 괜찮은듯

- 지도에서 좌표 이동하는 문제를 오랜만에 해서 행과 열이 헷갈렸다. 특히 class를 선언할때 int y,x 어떤게 행이고 열인지 꼼꼼히 확인할 필요가 있다.

 

5) 이 문제를 통해 얻어갈 것

삼성 SW역량테스트 A형(Advanced) 2문제 중 쉬운 문제로는 충분히 출제 가능한 난이도로 기본적인 BFS, Flood fill 에 대한 연습을 할 수 있었다.

 

기본에 충실하면서도 고슴도치와 홍수 2가지 조건이 동시에 flood fill이 진행됨에 따라 어떻게 처리를 할 것인가?

1) Queue를 2개로 만들기 2) Queue 1개로 순차 진행. 선택이 가능하고 

 

N이 매우 작아 성능은 여유 있지만, visit[ ][ ] 을 만들어서 처리할 경우 가지치기가 가능해 (고슴도치 방문했던 장소 방문 안 하기) 성능향상이 있기에 추가적으로 구현해볼만한 문제.

 

+ 지도에서 범위를 초과할 경우 예외처리 → 기본적이지만 항상 숙지!

 

 

C++ 코드 : 

// 탈출 3055 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <queue>

#define IMPOSSIBLE "KAKTUS"
#define MAX 51

using namespace std;

typedef pair<int, int> pii;			// 좌표정보 
int r, c;							// 지도 크기 R : 행, C : 열
char forest[MAX][MAX];				// 지도 정보
int time;							// 출력할 답

int visit[MAX][MAX];					// 방문 확인용
queue<pii> waterQueue, gosQueue;	// 물 queue, 고슴도치 queue

int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };

void input();
void bfs();
void output();

int main() {
	// 1. 입력을 받는다 
	//freopen("input.txt", "r", stdin);
	input();

	// 2. BFS를 실행한다.
	bfs();

	// 3. 답을 출력한다.
	output();
	
	return 0;
}

void input() {
	scanf("%d %d", &r, &c);
	// cin >> r >> c;

	// . 비어있는 곳 / * 물이 차있는 곳 / X 돌이 있는 곳
	// S 시작위치 / D 비버굴
	for (int i = 0; i < r; i++) {
		scanf("%s", forest[i]);
	}
}

void bfs() {
	// 1) 사전처리 - 고슴도치, 물 초기위치 확인
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (forest[i][j] == 'S') {
				gosQueue.push(pii(i, j));
				visit[i][j] = 1;
			}
			else if (forest[i][j] == '*') {
				waterQueue.push(pii(i, j));
			}
		}
	}

	// 2) 시간 순으로 확인
	for (time = 1; ; time++) {
		// 2-1) 물 채우기
		int waterSize = waterQueue.size();
		for (int i = 0; i < waterSize; i++) {
			pii cur = waterQueue.front();
			waterQueue.pop();

			// 사방으로 이동
			for (int j = 0; j < 4; j++) {
				int nr = cur.first + dr[j];
				int nc = cur.second + dc[j];

				// 지도 범위 초과시 continue
				if (nr < 0 || nc < 0 || nr >= r || nc >= c) continue;

				if (forest[nr][nc] == '.') {
					forest[nr][nc] = '*';
					waterQueue.push(pii(nr, nc)); 
				}
			}
		}

		// 2-2) 고슴도치 이동하기
		int gosSize = gosQueue.size();

		// 불가능한 경우 time 예외처리
		if (gosSize == 0) {
			time = -1;
			return;
		}

		for (int i = 0; i < gosSize; i++) {
			pii cur = gosQueue.front();
			gosQueue.pop();

			// 사방으로 이동
			for (int j = 0; j < 4; j++) {
				int nr = cur.first + dr[j];
				int nc = cur.second + dc[j];

				// 지도 범위 초과시 continue
				if (nr < 0 || nc < 0 || nr >= r || nc >= c) continue;

				// 도착했을 경우 탈출
				if (forest[nr][nc] == 'D') return;

				if (forest[nr][nc] == '.' && visit[nr][nc] == 0) {
					visit[nr][nc] = 1;
					gosQueue.push(pii(nr, nc));
				}
			}
		}

	}
}

void output() {
	if (time == -1) {
		printf("%s", IMPOSSIBLE);
		return;
	}
	printf("%d", time);
}
#endif