728x90
메모리: 10964 KB, 시간: 32 ms
너비 우선 탐색, 그래프 이론, 그래프 탐색
2025년 2월 26일 14:25:58
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
- #: 벽
- .: 지나갈 수 있는 공간
- J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
- F: 불이 난 공간
J는 입력에서 하나만 주어진다.
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;
int R, C;
char maze[1001][1001];
int Visited[1001][1001] = { 0, };
int VisitedFire[1001][1001] = { 0, };
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int iStartY, iStartX;
vector<pair<int, int>> vFire;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> R >> C;
for (int i = 0; i < R; ++i)
{
cin >> maze[i];
for (int j = 0; j < C; ++j)
{
if (maze[i][j] == 'J')
{
iStartY = i;
iStartX = j;
}
else if (maze[i][j] == 'F')
{
vFire.push_back({ i, j });
}
}
}
queue<pair<int, int>> Fq;
for (auto fire : vFire)
{
Fq.push(fire);
VisitedFire[fire.first][fire.second] = 1;
}
while (!Fq.empty())
{
int x, y;
tie(y, x) = Fq.front();
Fq.pop();
for (int i = 0; i < 4; ++i)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= R || nx >= C || maze[ny][nx] == '#')
continue;
if (VisitedFire[ny][nx] != 0)
continue;
VisitedFire[ny][nx] = VisitedFire[y][x] + 1;
Fq.push({ ny, nx });
}
}
queue<pair<int, int>> Jq;
Jq.push({ iStartY, iStartX });
Visited[iStartY][iStartX] = 1;
while (!Jq.empty())
{
int x, y;
tie(y, x) = Jq.front();
Jq.pop();
if (y == 0 || x == 0 || y == R - 1 || x == C - 1)
{
cout << Visited[y][x];
return 0;
}
for (int i = 0; i < 4; ++i)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= R || nx >= C || maze[ny][nx] == '#' || Visited[ny][nx] != 0 || VisitedFire[ny][nx] != 0 && VisitedFire[ny][nx] <= Visited[y][x] + 1)
continue;
Visited[ny][nx] = Visited[y][x] + 1;
Jq.push({ ny, nx });
}
}
cout << "IMPOSSIBLE";
return 0;
}
BFS 를 이용하여 풀이. 불기준 및 사람기준 둘다 BFS 를 해야한다. 그리고 메모리초과가 자주 떠서 조건을 까다롭게 하여 중복을 방지 하였다.
728x90
'프로그래밍 > 백준, 프로그래머스 문제 풀이' 카테고리의 다른 글
백준 16637 괄호추가하기 풀이(c++) (0) | 2025.02.26 |
---|---|
백준 12869번 뮤탈리스크 풀이(c++) (0) | 2025.02.26 |
백준 16234 인구이동 풀이(c++) (0) | 2025.02.26 |
백준 2589번 보물섬 풀이 (0) | 2025.02.26 |
백준 15686 치킨배달 풀이(c++) (0) | 2025.02.25 |
댓글