hwooo
BOJ (C/C++) 3055번: 탈출 본문
https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
풀이
이차원 배열을 사용하여 티떱숲의 지도를 저장한다. 이 때 물인 지점은 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;
}
'Study > Algorithm' 카테고리의 다른 글
BOJ (C/C++) 9205번: 맥주 마시며 걸어가기 (0) | 2023.04.26 |
---|---|
BOJ (C/C++) 14496번: 그대, 그머가 되어 (0) | 2023.04.25 |
BOJ (C/C++) 2156번: 포도주 시식 (0) | 2023.03.23 |
BOJ (C/C++) 1707번: 이분 그래프 (0) | 2023.03.23 |
BOJ (C/C++) 2250번: 트리의 높이와 너비 (0) | 2023.01.24 |