백준 3055_탈출 문제풀이 in C++
문제 URL
https://www.acmicpc.net/problem/3055
문제 요구사항
- 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다.
- 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
- 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 ‘.’로 표시되어 있고, 물이 차있는 지역은 ‘*’, 돌은 ‘X’로 표시되어 있다. 비버의 굴은 ‘D’로, 고슴도치의 위치는 ‘S’로 나타내어져 있다.
- 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다.
- (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다.
- 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다.
- 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
- 티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
- 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.
- 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
- 첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
- 다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. ‘D’와 ‘S’는 하나씩만 주어진다.
- 첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다.
- 만약, 안전하게 비버의 굴로 이동할 수 없다면, “KAKTUS”를 출력한다.
접근 방법
- 고슴도치와 물에 대해서 BFS를 수행하도록 하고, 고슴도치의 경우 탐색 시간을 구해야 하므로, checked ( int형 배열)을 이용해서 비용을 계산한다.
풀이 순서
- R과 C를 입력 받고 해당 크기만큼의 map 정보를 입력 받는다.
- 이때, 맵의 정보가 ‘D’일때, ‘S’일때, ‘*’ 일때 각각의 정보를 변수에 저장한다.
- BFS 수행
- hadge_q에 startX, startY를 넣고, visited의 startX, startY = true를 넣는다.
- hadge_q가 empty일 때까지 반복
- water_q의 사이즈만큼 for문을 반복하여 water에 대해서 먼저 bfs 전이 를 한다.
- 이후, hadge_q의 사이즈만큼 for문을 반복하여 1차 고슴도치 이동 bfs 탐색을 한다.
- 이때, 다음 방문 정점이 ‘D’라면 flag 변수에 true를 준다.
- 이와 같은 작업 반복
- flag가 true라면 checked의 endX, endY 좌표의 값을 출력, false라면 “KAKTUS” 출력
소스코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int R, C;
char map[50][50];
bool visited[50][50] = { false, };
int checked[50][50] = { 0, };
int startX, startY;
queue<pair<int, int>> water_q;
int endX, endY;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
bool flag = false;
void input() {
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> map[i][j];
if (map[i][j] == 'S') {
startX = i;
startY = j;
}
else if (map[i][j] == '*') {
water_q.push({ i, j });
}
else if (map[i][j] == 'D') {
endX = i;
endY = j;
}
}
}
}
void bfs() {
visited[startX][startY] = true;
queue<pair<int, int>> hadge_q;
hadge_q.push({ startX, startY });
int date_time = -1;
while (!hadge_q.empty()) {
if (flag)
return;
// 물 전이 시키고 시작함
int water_size = water_q.size();
for (int i = 0; i < water_size; i++) {
int w_x = water_q.front().first;
int w_y = water_q.front().second;
water_q.pop();
for (int j = 0; j < 4; j++) {
int next_w_x = w_x + dx[j];
int next_w_y = w_y + dy[j];
if (next_w_x >= 0 && next_w_y >= 0 && next_w_x < R && next_w_y < C) {
if (map[next_w_x][next_w_y] == '.') {
water_q.push({ next_w_x , next_w_y });
map[next_w_x][next_w_y] = '*';
}
}
}
}
int hadge_size = hadge_q.size();
for (int i = 0; i < hadge_size; i++) {
int h_x = hadge_q.front().first;
int h_y = hadge_q.front().second;
int now_cost = checked[h_x][h_y];
hadge_q.pop();
for (int i = 0; i < 4; i++) {
int next_h_x = h_x + dx[i];
int next_h_y = h_y + dy[i];
if (next_h_x >= 0 && next_h_y >= 0 && next_h_x < R && next_h_y < C) {
if (!visited[next_h_x][next_h_y] || checked[next_h_x][next_h_y] > now_cost + 1) {
if (map[next_h_x][next_h_y] == '.') {
visited[next_h_x][next_h_y] = true;
checked[next_h_x][next_h_y] = now_cost + 1;
hadge_q.push({ next_h_x , next_h_y });
}
else if (map[next_h_x][next_h_y] == 'D') {
checked[next_h_x][next_h_y] = now_cost + 1;
flag = true;
}
}
}
}
}
}
}
void solution() {
bfs();
}
void output() {
if (flag)
cout << checked[endX][endY];
else
cout << "KAKTUS";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solution();
output();
return 0;
}
문제 풀이 결과
