백준 - 4179번 불! (C++)

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

4179번: 불!

 

 

이 문제를 읽고 생각났던 것은 3차원 배열을 선언하여 그 상태 자체를 확인해야한다고 생각했다. 그러나 그러지 않아도 되었다. 

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

6087번: 레이저 통신

 

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

1600번: 말이 되고픈 원숭이

 

 

위 두 문제는 각 상태를 저장하고 3차원 배열을 사용하여 문제를 해결해야한다. 내가 불! 문제를 3차원 배열로 착각한 것은 사람이 가는 방향을 특정 상태라고 생각했기 때문이다. 

 

상태를 저장해야하는 문제의 경우 레이저 통신처럼 거울을 어떤 방향으로 놓아야하는지 , 즉 지금 x, y 에서 할 수 있는 상태 자체가 어려개라는 뜻이다.

 

말이 되고픈 원숭이의 경우도 지금 상태가 나이트 이동을 했을수도 있고 안했을 수도 있기 때문에 저장해놓는다.

 

하지만 이 불 문제는 무조건 동서남북으로 이동할 뿐, 지금 상태에서 어떤 행동을 저장해줄 필요는 없다. 그래서 불 -> 인간 순서로 bfs만 잘 지켜주면 쉽게 처리할 수 있는 문제이다.

 

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <queue>
#define MAX 1001
using namespace std;

queue<pair<pair<int, int>,pair<int, int>>> q; // x, y, cnt, 사람 or 불
bool fireState[MAX][MAX] = {false,};
bool moveState[MAX][MAX] = {false,};
int N, M;
int hx, hy;
char miro[MAX][MAX];

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

bool range(int x, int y){
    return x > -1 && x < N && y > -1 && y < M;
}

void bfs(){
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second.first;
        int t = q.front().second.second;
        q.pop();
        
        if((x == N - 1 || y == M - 1 || x == 0 || y == 0) && t == 0){
            cout << cnt + 1<< '\n';
            return;
        }
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(range(nx, ny) && miro[nx][ny] != '#' && !fireState[nx][ny]){
                if(t == 0) { // 인간
                    if(!moveState[nx][ny]){
                        moveState[nx][ny] = true;
                        q.push({{nx, ny},{cnt + 1, t}});
                    }
                }else{
                    fireState[nx][ny] = true;
                    q.push({{nx, ny}, {cnt, t}});
                }
            }
        }
    }
    
    cout << "IMPOSSIBLE" << '\n';
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        string str;
        cin >> str;

        for(int j = 0; j < M; j++){
            miro[i][j] = str[j];
            if(miro[i][j] == 'F') {
                q.push({{i, j}, {0, 1}});
                fireState[i][j] = true;
            }else if(miro[i][j] == 'J'){
                hx = i;
                hy = j;
            }
        }
    }
    
    q.push({{hx, hy},{0, 0}});
    bfs();

    return 0;
}