[C++] 백준 3055번 탈출

3055번: 탈출

4179번 불! 과 같은문제

[C++] 백준 4179번 불!

그래프 탐색을 두 종류로 나누어서 진행해주면 된다.

저 때 풀이와 완전 다르게 풀었다.

 

문제 풀이

다음과 같은 조건이 있다.

• 마법을 부려 숲에 홍수를 낸다.
• 1마리인 도치가 비버굴로 대피를 한다.
• 고슴도치는 상, 하, 좌, 우로 이동을 하는데 돌을 지날 수 없고
  물이 확장할 곳으로 이동할 수 없다.
• 물도 상, 하, 좌, 우로 이동을 하는데 돌 / 비버굴을 지나갈 수 없다.
• 입력은 다음과 같다
  '.' : 빈 곳
  '*' : 물
  'X' : 돌
  'D' : 비버굴
  'S' : 고슴도치의 위치

이 때 비버굴까지의 최소시간을 계산하면 된다.

 

나는 다음과 같은 순서로 그래프를 탐색하며 풀었다.

• 물을 먼저 이동시킨다. (이미 방문한 곳인지, 비버굴인지, 돌인지 Check)
  이 때 현재 지도의 정보를 나타내는 배열에 물의 정보를 업데이트 해준다.
• 도치를 이동시킨다. (이미 방문한 곳인지, 물인지, 돌인지 Check)
  이 때 현재 지도의 정보를 나타내는 배열에 도치의 정보는 필요없으므로 기록하지 않는다.
  만일 현재 좌표가 최초로 비버의 좌표라면 찾았다고 표시해준다.

둘 다 큐를 이용해서 BFS로 이동하되,

물은 한번에 이동하도록 Q[2501]의 형태로 만들었고, ([2501]은 0~ i까지의 시간에 물이 이동하는 것을 말한다.)

도치는 큐에 좌표와 해당 좌표까지 가는데 걸린 시간을 기록한다.

 

소스 코드

/*
* 백준 3055번 탈출
* https://www.acmicpc.net/problem/3055
* 그래프 탐색 - 너비 우선 탐색(BFS)
*/
#include <iostream>
#include <queue>

using namespace std;

queue<pair<pair<int, int>, int>> dochiQ;
queue<pair<int, int>> waterQ[2501];
int height, width;
pair<int, int> bieberHomePoint;
pair<int, int> dochiPoint;
char map[51][51];
bool dochiVisit[51][51];
bool waterVisit[51][51];
pair<int, int> directions[4] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1}
};
bool canFindTime;
int ans = 1000000000;

void findMinTime() {
	dochiVisit[dochiQ.front().first.first][dochiQ.front().first.second] = true;
	while (!dochiQ.empty()) {
		int dochiR = dochiQ.front().first.first;
		int dochiC = dochiQ.front().first.second;
		int arriveTime = dochiQ.front().second;
		dochiQ.pop();

		if (dochiR == bieberHomePoint.first && dochiC == bieberHomePoint.second) {
			ans = arriveTime;
			canFindTime = true;
			break;
		}

		while (!waterQ[arriveTime].empty()) {
			int waterR = waterQ[arriveTime].front().first;
			int waterC = waterQ[arriveTime].front().second;
			int nxtTime = arriveTime + 1;
			waterQ[arriveTime].pop();

			for (pair<int, int> dir : directions) {
				int nxtR = waterR + dir.first;
				int nxtC = waterC + dir.second;
				if (nxtR < 1 || nxtR > height || nxtC < 1 || nxtC > width ||
					waterVisit[nxtR][nxtC] || map[nxtR][nxtC] == 'D' || map[nxtR][nxtC] == 'X') {
					continue;
				}

				waterVisit[nxtR][nxtC] = true;
				map[nxtR][nxtC] = '*';
				waterQ[nxtTime].push({ nxtR, nxtC });
			}
		}

		for (pair<int, int> dir : directions) {
			int nxtR = dochiR + dir.first;
			int nxtC = dochiC + dir.second;

			if (nxtR < 1 || nxtR > height || nxtC < 1 || nxtC > width ||
				dochiVisit[nxtR][nxtC] || map[nxtR][nxtC] == 'X' || map[nxtR][nxtC] == '*') {
				continue;
			}

			dochiVisit[nxtR][nxtC] = true;
			dochiQ.push({ {nxtR, nxtC}, arriveTime + 1 });
		}
	}
}

int main() {
	cin >> height >> width;

	for (int i = 1; i <= height; i++) {
		for (int j = 1; j <= width; j++) {
			cin >> map[i][j];
			if (map[i][j] == '*') {
				waterQ[0].push({ i, j });
				waterVisit[i][j] = true;
			} else if (map[i][j] == 'S') {
				dochiQ.push({ { i, j }, 0 });
				map[i][j] = '.';
				dochiVisit[i][j] = true;
			}
			else if (map[i][j] == 'D') {
				bieberHomePoint.first = i;
				bieberHomePoint.second = j;
			}
		}
	}
	
	findMinTime();

	if (!canFindTime) {
		cout << "KAKTUS";
	}
	else {
		cout << ans;
	}

	return 0;
}

순서대로 그래프 탐색을 해주고, 방문 처리를 따로 잘 해주면 맞출 수 있는 문제.

 

GitHub - kimyunseok/cpp: C++로 코딩한 기록들을 담은 Repository입니다.