[BaekJoon 5427번] 불(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

5427번: 불

 

 

[문제 설명]

 

 

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

 

 

[입력]

 

 

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불

각 지도에 @의 개수는 하나이다.

 

 

[출력]

 

 

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

 

 

[입출력 예]

 

 

입력	출력
5 4 3 #### #*@. #### 7 6 ###.### #*#.#*# #.....# #.....# #..@..# ####### 7 4 ###.### #....*# #@....# .###### 5 5 ..... .***. .*@*. .***. ..... 3 3 ### #@# ###	2 5 IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE

 

 

[문제 풀이]

 

쉬운 문제인데.. 처음에 풀었을 때 메모리 초과가 났다.

메모리 초과가 왜 발생했지 코드를 보다가 도저히 모르겠어서 다시 풀기로 했다 ^ㅡ^

 

이 문제를 풀기 위해서는

빌딩 지도에 대한 입력을 저장할 배열

불의 위치 좌표에 대한 번지는 시간을 저장할 배열

상근이의 위치 좌표에 대한 탈출 시간을 저장할 배열

불의 위치 좌표를 저장할 큐

상근이의 위치 좌표를 저장할 큐

가 초기에 필요하다.

 

빌딩 지도에 대한 입력을 저장할 때

• 불이 번지는 위치 좌표에 대한 번지는 시간을 저장할 배열, 상근이의 위치 좌표에 대한 탈출 시간을 저장할 배열 두가지를  fill 함수를 통해 -1로 초기화 시킨다.
• 빌딩 지도 위치 좌표가 상근이의 위치('@') 이면 상근이의 위치 좌표를 저장할 큐에 넣는다. 그리고 상근이의 위치 좌표에 대한 탈출 시간을 0으로 저장한다.
• 빌딩 지도 위치 좌표가 불의 위치('*') 이면 불의 위치 좌표를 저장할 큐에 넣는다. 그리고 불의 위치 좌표에 대한 번지는 시간을 0으로 저장한다.

 

그리고 먼저 불에 대한 BFS 알고리즘을 사용하고,

아래 코드와 같이 다음 불의 위치 좌표 = 현재 불의 위치 좌표 + 1을 통해 불이 번진 시간을 계산해주었다.

fire_time[nx][ny] = fire_time[cur.first][cur.second} + 1;

// 불 시간 구하기
        while(!fire.empty()) {
            pair<int, int> cur = fire.front();
            fire.pop();
            for(int j = 0; j < 4; ++j) {
                int nx = cur.first + dx[j];
                int ny = cur.second + dy[j];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                // 빌딩 지도가 벽이거나, 불의 위치 좌표에 따른 번지는 시간이 초기값이 아니라면 
                // 이미 번진 위치이기 때문에 패스
                if((board[nx][ny] == '#') || (fire_time[nx][ny] != -1)) continue;
                fire.push({nx,ny});
                fire_time[nx][ny] = fire_time[cur.first][cur.second] + 1;
            }
        }

 

 

그리고 상근이에 대한 BFS 알고리즘을 사용했다.

상근이의 다음 위치를 계산할 때

다음 위치가 벽이거나 이미 방문했던 위치이면 갈 수 없고

불이 먼저 이동한 위치 또는 불과 동시에 이동한 위치로는 이동할 수 없기 때문에

 

아래와 같이 조건문을 넣음으로서 해결했다.

if((board[nx][ny] == '#') || (sangguen_time[nx][ny] != -1)) continue;

if((fire_time[nx][ny] != -1) && fire_time[nx][ny] <= sangguen_time[cur.first][cur.second] + 1) continue;

 

그리고 상근이가 탈출하기 위해선 다음 위치를 계산했을 때 빌딩의 지도 범위를 넘어간 경우 탈출 한 것으로 판단했다.

bool issuccess = false;
        while(!sangguen.empty()) {
            pair<int, int> cur = sangguen.front();
            sangguen.pop();
            for(int j = 0; j < 4; ++j) {
                int nx = cur.first + dx[j];
                int ny = cur.second + dy[j];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w) {
                    issuccess = true;
                    cout << sangguen_time[cur.first][cur.second] + 1 << '\n';
                    break;
                }
                if((board[nx][ny] == '#') || (sangguen_time[nx][ny] != -1)) continue;
                if((fire_time[nx][ny] != -1) && fire_time[nx][ny] <= sangguen_time[cur.first][cur.second] + 1) continue;
                sangguen.push({nx,ny});
                sangguen_time[nx][ny] = sangguen_time[cur.first][cur.second] + 1;
            }
            if(issuccess) break;
        }
        if(!issuccess) cout << "IMPOSSIBLE" << '\n';

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int fire_time[1001][1001];
int sangguen_time[1001][1001];
string board[1001];

int main(void) {
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i) {
        int w, h; // 빌딩 지도의 너비, 높이
        cin >> w >> h;
        queue<pair<int, int>> fire; // 불 좌표
        queue<pair<int, int>> sangguen; // 상근이 좌표

        for(int j = 0; j < h; ++j) {
            cin >> board[j];
            fill(fire_time[j], fire_time[j] + w, -1);
            fill(sangguen_time[j], sangguen_time[j] + w, -1);
            for(int k = 0; k < w; ++k) {
                if(board[j][k] == '@') {
                    sangguen.push({j,k});
                    sangguen_time[j][k] = 0;
                } else if(board[j][k] == '*') {
                    // 불 위치
                    fire.push({j,k});
                    fire_time[j][k] = 0;
                } else {}
            }
        }

        // 불 시간 구하기
        while(!fire.empty()) {
            pair<int, int> cur = fire.front();
            fire.pop();
            for(int j = 0; j < 4; ++j) {
                int nx = cur.first + dx[j];
                int ny = cur.second + dy[j];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if((board[nx][ny] == '#') || (fire_time[nx][ny] != -1)) continue;
                fire.push({nx,ny});
                fire_time[nx][ny] = fire_time[cur.first][cur.second] + 1;
            }
        }

        bool issuccess = false;
        while(!sangguen.empty()) {
            pair<int, int> cur = sangguen.front();
            sangguen.pop();
            for(int j = 0; j < 4; ++j) {
                int nx = cur.first + dx[j];
                int ny = cur.second + dy[j];
                if(nx < 0 || nx >= h || ny < 0 || ny >= w) {
                    issuccess = true;
                    cout << sangguen_time[cur.first][cur.second] + 1 << '\n';
                    break;
                }
                if((board[nx][ny] == '#') || (sangguen_time[nx][ny] != -1)) continue;
                if((fire_time[nx][ny] != -1) && fire_time[nx][ny] <= sangguen_time[cur.first][cur.second] + 1) continue;
                sangguen.push({nx,ny});
                sangguen_time[nx][ny] = sangguen_time[cur.first][cur.second] + 1;
            }
            if(issuccess) break;
        }
        if(!issuccess) cout << "IMPOSSIBLE" << '\n';
    }
    return 0;
}