[BOJ G4][C++] 백준 5427번 : 불

https://www.acmicpc.net/problem/5427

5427번: 불

 

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

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

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

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

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

출력

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

 

풀이

[🐕 Baaaaaarking/0x09강 - BFS] - [BOJ G4][C++] 백준 4179번: 불!

[BOJ G4][C++] 백준 4179번: 불!

4179번 의 다중케이스 버전.. 으로 쉽게 풀릴거라 생각했는데

아니였다ㅠㅠ

 

우선 잘 바꿔주고 예제도 다 맞았는데

 

넣자마자 0%에서 틀렸습니다

 

게시판을 찾아보니.. 배열 크기가 부족한거라 하더라..

그래서 배열 크기 바꿔줬더니

 

25%에서 틀렸습니다..

 

찾아보니 25%에서 틀리는 사람들이 상당히 많았다 ㅎㅎ

슬픈 영혼들 ㅠㅠ

다행히 게시판 정독 끝에 테스트케이스를 돌때마다 큐를 비워주지 않았기 때문에 생긴 일이라는걸 알 수 있었다!

 

https://www.acmicpc.net/board/view/71789

글 읽기 - 아래 글들 참고 해도 25%에서 걸리는 분들 보세요

짧지만 감사한 게시판 글 하나..

좋아요 감사히 누르고 해결했다..

 

// Authored by : seondal
// 풀이 : https://whkakrkr.tistory.com/
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>

using namespace std;

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

queue<pair<int, int>> q;
queue<pair<int, int>> s;

char board[1002][1002];
int fire[1002][1002];
int jihun[1002][1002];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        // 초기화
        bool success = false;
        while(!q.empty()) q.pop();
        while(!s.empty()) s.pop();
        
        // 입력 받기
        int r,c;
        cin >> c >> r;
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                cin >> board[i][j];
                
                fire[i][j] = -1;
                jihun[i][j] = -1;
                
                if(board[i][j] == '*'){
                    q.push({i,j});
                    fire[i][j] = 0;
                }
                if(board[i][j] == '@') {
                    s.push({i,j});
                    jihun[i][j] = 0;
                }
            }
        }
        
        // 시간에 따른 불의 위치
        while(!q.empty()){
            pair<int, int> current = q.front();
            q.pop();
            
            for(int dir=0; dir<4; dir++){
                int x = current.first + dx[dir];
                int y = current.second + dy[dir];
                
                if(x<0 || x>=r || y<0 || y>=c) continue;
                if(fire[x][y] >= 0 || board[x][y] == '#') continue; // 이미 불이 있거나 벽이라면 패스
                
                fire[x][y] = fire[current.first][current.second] + 1;
                q.push({x,y});
            }
        }
        
        // 시간에 따른 지훈이의 위치
        while(!s.empty() && !success) {
            pair<int, int> current = s.front();
            s.pop();
            
            for(int dir=0; dir<4; dir++){
                int x = current.first + dx[dir];
                int y = current.second + dy[dir];
                
                // 미로 탈출시 종료
                if(x<0 || x>=r || y<0 || y>=c) {
                    cout << jihun[current.first][current.second] + 1 << "\n";
                    success = true;
                    break;
                }
                
                // 이미 방문했거나 벽이 있으면 패스
                if(jihun[x][y] >= 0 || board[x][y] == '#') continue;
                
                // 가려는 곳에 불이 이미 있다면 패스
                if(fire[x][y] != -1 && jihun[current.first][current.second] + 1 >= fire[x][y]) continue;
                
                jihun[x][y] = jihun[current.first][current.second] + 1;
                s.push({x,y});
            }
        }
        
        // 탈출 실패
        if(!success)
            cout << "IMPOSSIBLE\n";
    }
        return 0;
}

/*
 */