4179번 불! - C++

✅️[문제]
https://www.acmicpc.net/problem/4179

4179번: 불!

✅️[풀이]

불과 지훈이의 좌표를 따로 큐에 넣어 각각 BFS를 돌리면 된다!
❗️주의할점은 지훈이의 좌표보다 불의 좌표를 큐에 먼저 넣어야 되는 점이다. 왜냐하면, 지훈이의 맨 처음 좌표가 가장자리에 있는 경우라면 지훈이의 탈출 최소 경로가 잘못되어 계산할 수 있기 때문이다.
❗️지훈이와 불의 방문 여부를 체크하지 않으면 시간초과가 날 수 있으므로 주의하자!
✔️ 지훈이의 현재 좌표가 가장자리에 도달한 경우 현재 좌표의 누적 값을 출력한뒤 종료 시킨다!
✔️ 만약 for문을 통과하여, 프로그램의 끝에 도달한 경우 IMPOSSIBLE을 출력해주면 된다.

✅️[코드]

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

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

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

string board[1002];

int vis[1002][1002];

bool vis2[1002][1002][2];

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    

    int m,n;

    cin >> n >> m;

    

    queue<pair<int,int>> Q;

    

    for(int i=0; i<n; i++){

        cin >> board[i];

    }

    int x,y;

    for(int i=0; i<n; i++){

        for(int j=0; j<m; j++){

            if(board[i][j] == 'J') {

                vis2[i][j][0] = 1;

                vis[i][j] = 1;

                x = i;

                y = j;

            }

            if(board[i][j] == 'F'){

                vis2[i][j][1] = 1;

                Q.push({i,j});

            }

        }

    }

    Q.push({x,y});

            

            while(!Q.empty()){

                pair<int,int> q2 = Q.front(); Q.pop();

                if(board[q2.X][q2.Y] == 'J'){

                    if(q2.X == 0 || q2.X == n-1 || q2.Y == 0 || q2.Y == m-1){

                        cout << vis[q2.X][q2.Y];

                        return 0;

                    }

                  for(int i=0; i<4; i++){

                      int x = q2.X + dx[i];

                      int y = q2.Y + dy[i];

                    

                      if(x < 0 || x >= n || y < 0 || y >= m) continue;

                      if(board[x][y] != '.' || vis2[x][y][0]) continue;

                      board[x][y] = 'J';

                      vis[x][y] = vis[q2.X][q2.Y] + 1;

                      vis2[x][y][0] = 1;

                      Q.push({x,y});

                   }

                }

                else if(board[q2.X][q2.Y] == 'F'){

                    for(int i=0; i<4; i++){

                        int x = q2.X + dx[i];

                        int y = q2.Y + dy[i];

                        

                        if(x<0 || x >= n || y <0 || y >= m) continue;

                        if(board[x][y] == '#' || board[x][y] == 'J' || vis2[x][y][1]) continue;

                        board[x][y] = 'F';

                        vis2[x][y][1] = 1;

                        Q.push({x,y});

                    }

                }

            }

    cout << "IMPOSSIBLE";

    

}

✅️[소감]
🔥 🔥 🔥
BFS는 풀면 풀수록 재미있다!