백준 5427 / 불

BFS 문제

야마돌게하는 반례 때문에 한창을 헤맸다.

1

3 3

* * *

* * *

* @ *

바로 나갈 수 있는 경우....

바로 나갈 수 있으면 문제를 안내지 않았을까.....

https://www.youtube.com/watch?v=w211KOQ5BMI

이런 어이없는 반례들까지 모두 해결할 수 있게끔 알고리즘을 완벽히 세워야겠다.

------------------------------

'불' 문제와 비슷한 문제가 있었다. 너구린가 고슴도친가가 어딜 빠져나가는 문제.

이런 문제는 문제를 잘 읽고, 

불을 먼저 이동시켜야하는지 사람을 먼지 이동시켜야하는지 파악해야한다.

이 문제는 불을 먼저 이동시켜야하므로 (물론 사람을 이동시킨후 불이 사람을 잡아먹게(?)해도 풀 수 있을 듯)

불의 위치를 먼저 큐에 넣었다.

테스트 케이스가 여러개인 문제는 꼭! 초기화를 잘 해주어야한다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <memory.h>
 
using namespace std;
 
 
char map[1001][1001];
bool fcheck[1001][1001];
bool pcheck[1001][1001];
 
int d[1001][1001];
 
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
 
int main() {
    
    //freopen("Text.txt", "r", stdin);
 
    int testcase;
    int n, m;
 
 
    cin >> testcase;
 
 
 
 
    while (testcase--) {
        bool onestepout = false;
        cin >> m >> n;
 
 
 
        queue<tuple<int, int, int>>q;
        vector<pair<int, int>>ext;
 
        memset(fcheck, false, sizeof(fcheck));
        memset(pcheck, false, sizeof(pcheck));
        memset(d, 0, sizeof(d));
            
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> map[i][j];
                if (map[i][j] == '*') {
                    q.push(make_tuple(i, j, 0)); //불
                    fcheck[i][j] = true;
                }
 
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    if (map[i][j] == '.') {
 
                        ext.push_back(make_pair(i, j));
                    }
                }
            }
        }
 
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == '@') {
                    if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                        onestepout = true;
 
                    }
                    else {
                        q.push(make_tuple(i, j, 1)); //사람
                        pcheck[i][j] = true;
                    }
                }
            }
        }
 
        while (!q.empty()) {
            int x, y, who;
            tie(x, y, who) = q.front();
            q.pop();
 
 
            if (who == 0) {
 
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n &&ny < m) {
                        if (fcheck[nx][ny] == false && map[nx][ny] != '#' && map[nx][ny]!= '*'){
                            fcheck[nx][ny] = true;
                            map[nx][ny] = '*';
                            q.push(make_tuple(nx, ny, 0));
                        }
                    }
                }
            }
 
            if (who == 1) {
 
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && ny >= 0 && nx < n &&ny < m) {
                        if (pcheck[nx][ny] == false && map[nx][ny] == '.') {
                            pcheck[nx][ny] = true;
                            d[nx][ny] = d[x][y] + 1;
                            q.push(make_tuple(nx, ny, 1));
                        }
                    }
                }
            }
 
 
 
 
 
 
        }
 
        vector<int>ans;
 
 
        for (int i = 0; i < ext.size(); i++) {
            int x, y;
            x = ext[i].first;
            y = ext[i].second;
 
            if (d[x][y] != 0) {
                ans.push_back(d[x][y]);
            }
 
        }
        sort(ans.begin(), ans.end());
 
 
        if (n == 1 && m == 1 || onestepout ==true) {
            cout << 1 << endl;
 
        }
        else{
            if (ans.empty()) {
                cout << "IMPOSSIBLE" << endl;
            }
            else {
                cout << ans[0] + 1 << endl;
            }
 
        }
 
        while (!q.empty()) {
            q.pop();
        }
 
 
    }
 
}