취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3055번 문제인 탈출이다.
문제는 아래 링크를 확인하자.

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

매 시간마다 물이 새로 차오르는 칸을 먼저 채우고, 그다음으로 고슴도치가 안전하게 이동할 수 있는 칸을 채우는 식으로 접근하자.

bfs를 이용해 단계별로 물과 고슴도치의 이동을 시뮬레이션해나가자. bfs 과정에서 각 과정 시작 전 큐에 들어있는 좌표의 수가 해당 단계에서 퍼뜨려야 하는 좌표의 개수이므로 이를 이용해 구현을 편하게 할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int R, C;
int sR, sC, eR, eC;
string board[50];
queue<pair<int, int>> que1, que2; // S, '*'

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

void bfs() {
	que1.push(make_pair(sR, sC));
	dist[sR][sC] = 1;
	while (!que1.empty()) {
		int que2size = que2.size();
		while (que2size--) {
			int r = que2.front().first, c = que2.front().second; que2.pop();
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
				if (board[rr][cc] == '.' || board[rr][cc] == 'S') {
					board[rr][cc] = '*';
					que2.push(make_pair(rr, cc));
				}
			}
		}
		int que1size = que1.size();
		while (que1size--) {
			int r = que1.front().first, c = que1.front().second; que1.pop();
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
				if (dist[rr][cc] || board[rr][cc] == '*' || board[rr][cc] == 'X') continue;
				dist[rr][cc] = dist[r][c] + 1;
				que1.push(make_pair(rr, cc));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == '*') que2.push(make_pair(r, c));
			else if (board[r][c] == 'S') sR = r, sC = c;
			else if (board[r][c] == 'D') eR = r, eC = c;
		}
	}

	bfs();

	if (dist[eR][eC]) cout << dist[eR][eC] - 1;
	else cout << "KAKTUS";
}