[백준/C++] 5427번. 불
[백준/C++] 5427번. 불
1. 문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- '.': 빈 공간
- '#': 벽
- '@': 상근이의 시작 위치
- '*': 불
각 지도에 @의 개수는 하나이다.
3. 출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
4. 풀이
BFS
로 풀었다.- 각 테스트 케이스마다
BFS
를 하였다. - 우선, 지도를 탐색하며 불의 위치와 상근이의 시작 위치를 모두 큐에 삽입한다.
- 이때, 상근이의 위치는 불의 위치를 모두 삽입한 후에 삽입한다.
- 상근이는 불이 번질 위치에도 가면 안되기 때문에 불이 번지는 작업을 먼저하고 상근이의 이동작업을 처리하기 위함이다.
- 큐에 삽입하였을때 불인지 상근인지 구분하는
type
을 추가해서 큐에 삽입한다.
- 큐에서 하나씩 꺼내서 작업을 진행한다.
- 불과 상근이 모두 이미 불이 있는 곳과 벽으로는 이동할 수 없기 때문에 벽이 거나 이미 불이 번진 곳은
continue
로 무시한다. - 이동할 곳이 벽이 아니고 불이 번진 곳도 아닌 경우,
- 이동할 주체가 불인 경우
map
에서 이동할 위치를 불로 바꾸고 큐에 삽입한다. - 이동할 주체가 상근이인 경우 이미 방문한 적이 있으면 무시하고 그렇지 않으면
route
배열의 값을 변경하고 큐에 삽입한다.
- 이동할 주체가 불인 경우
- 큐에서 꺼낸 값이 배열의 테투리인 경우 현재
route + 1
한 값을 리턴한다. while-loop
가 끝날 때까지 탈출하지 못하면INF
값을 리턴한다.
5. 처음 코드와 달라진 점
- 상근이의 위치를 찾고 나서 해당 위치를
.
으로 표시하도록 변경하였다. - 이동할 위치를 구하는 수식을 잘못 써서 변경하였다.
6. 코드
#include <iostream>
#include <algorithm>
#include <queue>
#define INF 987654321
using namespace std;
int n, m;
char map[1000][1000];
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
int bfs() {
int route[1000][1000] = {0, };
queue<pair<int, pair<int, int> > > q;
int startX, startY;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == '@') {
startX = i;
startY = j;
map[i][j] = '.';
}
else if (map[i][j] == '*') {
q.push(make_pair(1, make_pair(i, j)));
}
}
}
q.push(make_pair(0, make_pair(startX, startY)));
while (!q.empty()) {
int type = q.front().first;
int x = q.front().second.first;
int y = q.front().second.second;
q.pop();
if (type == 0 && (x == 0 || x == n - 1 || y == 0 || y == m - 1)) return route[x][y] + 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (map[nx][ny] == '#' || map[nx][ny] == '*') continue;
if (type == 0) {
if (route[nx][ny] != 0 || (nx == startX && ny == startY)) continue;
route[nx][ny] = route[x][y] + 1;
q.push(make_pair(type, make_pair(nx, ny)));
}
else {
map[nx][ny] = '*';
q.push(make_pair(type, make_pair(nx, ny)));
}
}
}
return INF;
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
cin >> m >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
}
}
int answer = bfs();
if (answer == INF) cout << "IMPOSSIBLE\n";
else cout << answer << endl;
}
}
Author And Source
이 문제에 관하여([백준/C++] 5427번. 불), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/boj5427저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)