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

[문제]

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

4179번: 불!

 

[문제 풀이]

문제 조건 제한이 까다로워 실수가 많았던 문제.

BFS 에 익숙하지 않다 보니 초반에 코드가 더러워서 보기가 힘들었던 부분이 많았다.

BFS나 DFS등을 쓸 때는 변수명을 잘 지으면서 최대한 코드를 보기 편하게 만들자.

 

먼저 불꽃이 가는 곳을 모두 만들고 다음으로 지훈이를 옮기자.

* 팁 : 불꽃이 가는 곳은 기본 미로가 아닌 다른 불꽃 미로를 만들어두자. 안 그러면 나중에 지훈이가 미로를 돌아다닐때 비교하기가 힘들어진다. 나중에 익숙해지면 미로 하나에 넣을 수 있을테지만 우선은 따로 만들어서 연습을 해보자.

 

[새로 배운 문법]

pair<pair<int,int>, int>

pair 안에 pair를 놨둠으로서 tuple을 대신 할 수 있다.

gcc 11 이하의 경우에는 tuple을 사용할 수 없으니 해당 방법을 익혀두는 것도 나쁘지 않을 것.

[코드]

#include<iostream>
#include<queue>
#include<vector>
#define endl "\n"

using namespace std;

int fire_visit[1001][1001];

void fire_bfs(vector<vector<char> >& maze, queue<pair<int, int> > fire, int r, int c){
    fire_visit[fire.front().first][fire.front().second] = 0;
    int dict[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

    while(fire.size()>0){
        int fire_size = fire.size();
        while(fire_size--){
            
            int fire_x = fire.front().first;
            int fire_y = fire.front().second;
            fire.pop();

            for(int i = 0;i<4;i++){
                int next_x = fire_x + dict[i][0];
                int next_y = fire_y + dict[i][1];

                if(next_x >= 0 and next_x < r and next_y >= 0 and next_y < c){
                    if(maze[next_x][next_y] != '#'){
                        if(fire_visit[next_x][next_y] > fire_visit[fire_x][fire_y] + 1){
                            fire_visit[next_x][next_y] = fire_visit[fire_x][fire_y] + 1;
                            fire.push(make_pair(next_x, next_y));
                        }
                    }
                }
            }
        }
    }
    return;
}

int bfs(vector<vector<char> > maze, queue<pair<pair<int, int>, int > > jihhon, int r, int c){
    vector<vector<int> > visit(r, vector<int>(c, 0));
    visit[jihhon.front().first.first][jihhon.front().first.second] = 1;

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

    while(jihhon.size()>0){

            // cout<<"jihoon_x : "<<jihhon.front().first.first<<endl;
            // cout<<"jihoon_y ; "<<jihhon.front().first.second<<endl;

            int jihoon_x = jihhon.front().first.first;
            int jihoon_y = jihhon.front().first.second;
            int jihoon_num = jihhon.front().second;
            jihhon.pop();

            if(jihoon_x == 0 or jihoon_x == r-1 or jihoon_y == 0 or jihoon_y == c-1){
                return jihoon_num + 1;
            }

            for(int i = 0;i<4;i++){
                int next_x = jihoon_x + dict[i][0];
                int next_y = jihoon_y + dict[i][1];

            if(next_x >= 0 and next_x <r and next_y >= 0 and next_y < c){
                if(visit[next_x][next_y] == 0){
                    if(fire_visit[next_x][next_y] > jihoon_num + 1 and maze[next_x][next_y] != '#'){
                        visit[next_x][next_y] = 1;
                        jihhon.push(make_pair(make_pair(next_x, next_y), jihoon_num + 1));
                    }
                }
            }
        }        
    }

    return 0 ;
}

int main(){
    
    int r, c;
    cin>>r>>c;

    vector<vector<char> > maze(r, vector<char>(c,0));
    queue<pair<pair<int, int>,int> > jihoon;
    queue<pair<int ,int> > fire;

    for(int i = 0;i<r;i++){
        for(int j = 0;j<c;j++){
            cin>>maze[i][j];
            if(maze[i][j] == 'J'){
                jihoon.push(make_pair(make_pair(i,j),0));
            }
            else if(maze[i][j] == 'F'){
                fire.push(make_pair(i,j));
                fire_visit[i][j] = 0;
            }
            else{
                fire_visit[i][j] = 9999;
            }
        }
    }

    if(fire.size() > 0){
        fire_bfs(maze,fire,r,c);
    }
    
    int answer = bfs(maze,jihoon,r,c);

    if(answer > 0){
        cout<<answer<<endl;
    }
    else{
        cout<<"IMPOSSIBLE"<<endl;
    }

    return 0;
}