[백준] 4179 불!(C++)

4179번: 불! (acmicpc.net)

4179번: 불!

---

난이도 : 골드 4

 

풀이 과정 :

arr 배열을 선언을 해줘서 입력을 받을 때

#(벽)은 0, .(길), J(지훈)은 1, F(불)은 -1로  초기화를 시켜줬다.

나중에 다른 사람 풀이 과정을 보면 불 bfs를 돌리고 지훈이 bfs를 돌려줬는데

나는 불과 지훈이를 bfs를 동시에 돌리면서 bfs를 돌릴때 전 x, y값을 기준으로 지훈이인지 불인지를 체크하며 돌렸다.

흐름은 이렇다.

 

먼저 arr 초기화 과정에서 불의 위치를 먼저 큐에 넣어주고,

지훈이 위치는 불의 위치를 다 큐에 넣어준 후에 큐에 넣어준다.

그러면 불이 먼저 돌고 지훈이가 돌게된다.

 

그 후 bfs돌릴때 x,y(전 좌표)가 -1 즉 불일 때는 다음에 돌 nx, ny가 -1이 되도록해주고

arr[x][y]가 1이상일때는 지훈이가 bfs도는 중이기 때문에 그전값에 +1 해준다.

그리고 만약 가장자리에 도착햇을 때 x == 0 || ny == 0 || nx == n - 1 || ny == m - 1

일때는 바로 return 해줘서 bfs를 빠져나오면 된다.

이 때 가장자리에 오는 경우가 여러번일 수가 있어서 min을 사용하여 최솟값을 출력하게 했다.

(그냥 처음 가장자리 올때가 최단거리일거같은데 min을 안쓰면 틀리다고 나온다.

처음 가장자리온게 꼭 최솟값은 아닌거같다..)

 

이렇게 풀고 예외 조건 들이 굉장히 많았는데 

게시판 반례를 보면서 찾아본거 ! 대표적인거는

 

첫번째 반례)

불이랑 지훈이 위치가 같은게 주어졌을 때 bfs를 안돌아도된다. (58번째 줄 예외처리)

 

두번째 반례)

bfs 도려는 nx, ny가 지훈이초기좌표 로 돌게 될때를 막아줘야 한다. (21번째줄 예외처리)

 

 

 

전체 코드 :

#include <iostream>
#include <algorithm> 
#include <queue>
#include <string>
using namespace std;

int n, m, ans= 1e9, arr[1005][1005], sx, sy; // 0 벽, 1 길, -1 불
queue<pair<int, int>> q;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };


void bfs() {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        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 && arr[nx][ny] == 1 && !( nx == sx && ny == sy )) {
                if (arr[x][y] == -1) {
                    arr[nx][ny] = -1;
                    q.push(make_pair(nx, ny));
                }
                else if (arr[x][y] > 0) { //사람일때
                    arr[nx][ny] = arr[x][y] + 1;
                    if (nx == 0 || ny == 0 || nx == n - 1 || ny == m - 1) {
                        ans = min(ans, arr[nx][ny]);
                        return;
                    }
                    q.push(make_pair(nx, ny));
                }
                
            }
        }

        
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == '#') arr[i][j] = 0;
            else if (s[j] == '.') arr[i][j] = 1;
            else if (s[j] == 'F') {
                arr[i][j] = -1;
                q.push(make_pair(i, j));
            }
            else {
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                    cout << "1";
                    return 0;
                }
                sx = i, sy = j;
                arr[i][j] = 1;
            }
        }
    }

    q.push(make_pair(sx, sy));
    bfs();

    if (ans == 1e9) cout << "IMPOSSIBLE";
    else  cout << ans;
    
}