[백준][C++] 5427: 불 (bfs)

문제

5427

풀이

• 전형적인 bfs 문제이지만 처리해야할게 하나 더 있다.
• 탈출하려는 사람이 먼저 움직여야 한다는 것이다. (아니면 가장 마지막에)
• 그 이유는 다음과 같다.
  • 현재 상태에서 불이 이동하는 위치는 현재 사람의 위치에 올 수 있다. 그래도 현재 사람은 이동할 수 있다.
  • 불이 먼저 이동하면, 아무런 검사를 하지 않아도 된다.
  • 사람이 먼저 이동하면, 다음 상태에서 불이 붙었는지 검사해야한다. (이동한 위치에 불도 그 위치에 옮겨 붙음)
  • 중간에 끼어서 이동하면, 먼저 움직인 불은 신경쓰지 않아도 되지만, 후에 움직인 불은 신경써야한다. 그렇기 때문에 이를 처리하는 코드를 추가해야하며, 이를 구별하기는 까다롭다. (만약 사람이 있는 타일에 불이 붙으면, 먼저움직인 불은 제외하고 후에 움직인 불을 처리해야함)
• 그렇기 때문에 deque로 사람을 앞에 추가하였다.

코드

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

deque<tuple<int, int, int, char> > q;
        int r, c;
char board[1001][1001];

int bfs() {
    while(!q.empty()){
        auto [y, x, day, what] = q.front();
        q.pop_front();
        for(int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if(what == '@'&&board[y][x] == '*') {
                continue;
            }
            if(yy < 0|| yy >= r||
               xx < 0|| xx >=c) {
                if(what == '@') {
                    return day + 1;
                }
                   continue;
            }

            if(board[yy][xx] == '.' ||(board[yy][xx] =='@' && what == '*')) {
                board[yy][xx] = what;
                q.push_back({yy, xx, day+1, what});
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        cin>>c>>r;
        q.clear();
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                cin>>board[i][j];
                if(board[i][j] == '*') {
                    q.push_back({i, j, 0, '*'});
                }
                if (board[i][j] =='@'){
                    q.push_front({i, j, 0, '@'});
                }
            }
        }
        int answer = bfs();
        if(answer == -1) {
            cout<<"IMPOSSIBLE\n";
        }
        else {
            cout<<answer<<"\n";
        }
    }
}

• 아래는 사람을 나중에 이동시킨 것이다.

deque<tuple<int, int, int, char> > q;
        int r, c;
char board[1001][1001];

int bfs() {
    while(!q.empty()){
        auto [y, x, day, what] = q.front();
        q.pop_front();
        for(int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if(yy < 0|| yy >= r||
               xx < 0|| xx >=c) {
                if(what == '@') {
                    return day + 1;
                }
                   continue;
            }

            if(board[yy][xx] == '.' ||(board[yy][xx] =='@' && what == '*')) {
                board[yy][xx] = what;
                q.push_back({yy, xx, day+1, what});
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        cin>>c>>r;
        q.clear();
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                cin>>board[i][j];
                if(board[i][j] == '*') {
                    q.push_front({i, j, 0, '*'});
                }
                if (board[i][j] =='@'){
                    q.push_back({i, j, 0, '@'});
                }
            }
        }
        int answer = bfs();
        if(answer == -1) {
            cout<<"IMPOSSIBLE\n";
        }
        else {
            cout<<answer<<"\n";
        }
    }
}