BOJ 5427

문제출처

  • 이전 포스트에서 2번문제를 구현하는데 도움이 될만한 문제를 baarkingdog님이 추천해주셔서 풀이를 진행하게 되었습니다.

문제 해석

  • 상근이가 불을 피해서 최대한 빨리 탈출할 수 있는 경우를 구하는 문제입니다.
  • 불과 상근이는 인접한 빈 공간으로 퍼져나가는데 모두 벽을 통과할 수 없고, 상근이는 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없습니다.
  • 1<=w,h< 1000

설계(5)

  • 두개의 큐를 이용한 bfs응용문제입니다.
  • 먼저 불을 이동시킨 후, 상근이가 이동할 수 있는 곳으로 이동합니다.
  • 불은 빈 공간으로 이동 후, 불표시를 해줍니다.
  • 상근이는 빈 공간이고 방문하지 않은 곳으로 이동이 가능합니다.
  • 좌표의 끝에 도달했으면 해당 cnt값을 리턴합니다.

구현(10)

코드
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 1000
typedef pair<int,int> P;
char map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int N,M;
queue<P> q,fire;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int bfs(){
    int cnt = 0;
    while (!q.empty()){
        int q_size = fire.size();
        while (q_size--){
            int x = fire.front().first;
            int y = fire.front().second;
            fire.pop();
            for (int k = 0; k<4; k++){
                int nx = x+dx[k];
                int ny = y + dy[k];
                if (nx < 0 || ny < 0||nx>=N || ny>=M) continue;
                if (map[nx][ny]=='.'){
                    map[nx][ny] = '*';
                    fire.push({nx,ny});
                }
            }
        }
        q_size = q.size();
        while (q_size--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (x == 0 || y == 0 || x == N-1 || y == M - 1) return cnt+1;
            for (int k = 0; k < 4; k++){
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx>=N || ny>=M) continue;
                if (map[nx][ny] =='.' && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    q.push({nx,ny});
                }  
            }
        }
        cnt++;
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;

    cin >> t;
    while (t--){
        memset(visited,false,sizeof(visited));
        while (!q.empty()) q.pop();
        while (!fire.empty()) fire.pop();
        cin >> M >> N;
        for (int i = 0; i < N; i++){
            cin >> map[i];
            for (int j= 0;j<M; j++){
                if (map[i][j] == '*'){
                    fire.push({i,j});
                }
                else if (map[i][j]=='@'){
                    q.push({i,j});
                    map[i][j] ='.';
                    visited[i][j] = true;
                }
            }
        }
        int ans = bfs();
        if (ans ==-1) cout << "IMPOSSIBLE"<<"\n";
        else cout << ans <<"\n";
    }
    return 0;
}
디버깅
  • 문제는 아주 쉬웠습니다만, 입력을 하는 방식에 따라 실행시간이 천차만별인 것을 알수 있었습니다.
  • 모든 N,M을 돌면서 입력을 받는 경우보다, N줄을 한번에 받는 경우 거의 90ms가량 시간이 압축이 됩니다.
제출결과
  • 40ms

마무리

  • bfs응용문제였습니다. 위 방법을 이용해서 이전에 포스트한 대회의 문제를 다시 풀이해봐야 할 것 같습니다.