BOJ (C/C++) 3055번: 탈출

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

3055번: 탈출

---

풀이

이차원 배열을 사용하여 티떱숲의 지도를 저장한다. 이 때 물인 지점은 W에 저장하고 도착지와 돌의 위치는 음수로, 빈 칸은 양수로 저장

 

Water 함수 : 해당 지점에 물이 차오르는 시점을 저장 - BFS입력 시에 저장했던 물의 위치를 시작으로 맵의 모든 지점을 탐색

 

Route 함수: 시작지점(S) 부터 해당지점에 도달하는 시점을 저장 - BFS물이 차있거나 찰 예정인 지점은 갈 수 없음탐색 중 도착지를 만났다면 해당 시간을, 만나지 못했다면 KAKTUS 출력

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

queue <pair<int, int>> W, Q;

// map[][] : 티떱숲의 지도, 물이 차는 시점 저장
// route[][] : 해당 지점에 도달하는 시점 저장
int map[50][50], route[50][50]; 
bool visited[50][50];


// 해당 지점에 물이 차는 시점 저장 map[][]
void Water(int R, int C) {
	int x, y, nx, ny;
	int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };

	while (!W.empty()) {
		x = W.front().first, y = W.front().second;
		W.pop();

		for (int i = 0; i < 4; i++) {
			nx = x + dx[i], ny = y + dy[i];
			if (visited[nx][ny] || map[nx][ny] < 0 || nx < 0 || nx >= R || ny < 0 || ny >= C) continue;

			visited[nx][ny] = true;
			map[nx][ny] = map[x][y] + 1;
			W.push({ nx,ny });
		}
	}
}

void Route(int R, int C) {
	int x, y, nx, ny;
	int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };

	visited[Q.front().first][Q.front().second] = true;
	while (!Q.empty()) {
		x = Q.front().first, y = Q.front().second;
		Q.pop();

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

			// 비버 굴에 도착할 때의 시간 출력
			if (map[nx][ny] == -3) {
				printf("%d", route[x][y] + 1);
				return;
			}

			// map[nx][ny] <= 0 : 갈 수 없는 곳, 돌
			if (visited[nx][ny] || map[nx][ny] <= 0 || nx < 0 || nx >= R || ny < 0 || ny >= C) continue;

			visited[nx][ny] = true;
			route[nx][ny] = route[x][y] + 1;

			// 해당 지점에 물이 차는 시점 > 해당 지점에 가는 시점이면 그 길은 갈 수 있음
			// 물이 찰 예정인 칸으로 이동할 수 없으므로 등호(=)는 들어가지 않음
			if (map[nx][ny] > route[nx][ny]) Q.push({ nx,ny });
		}
	}

	// 비버 굴에 도달할 수 없으므로 KAKTUS 출력
	printf("KAKTUS");
	return;
}
int main() {
	int R, C;
	char s[51];

	// input
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		scanf("%s", s);
		for (int j = 0; j < C; j++) {

			// 고슴도치 위치, 출발지
			if (s[j] == 'S') Q.push({ i,j });
			else if (s[j] == 'D') map[i][j] = -3; // 비버 굴, 도착지
			else if (s[j] == 'X') map[i][j] = -1; // stone

			else if (s[j] == '*') { // water
				map[i][j] = 0;
				W.push({ i,j });
				visited[i][j] = true;
			}

			// 빈 공간
			else map[i][j] = 100;
		}
	}

	Water(R, C);
	fill(visited[0], visited[50], false);
	Route(R, C);

	return 0;
}