문제

Code

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

char board[1002][1002];
int dist1[1002][1002];
int dist2[1002][1002];
#define X first
#define Y second
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int R, C;
    queue<pair<int,int>> Q1,Q2;

    cin >> R >> C;

    for(int i=0;i<R;i++)
    {
        fill(dist1[i], dist1[i]+C, -1);
        fill(dist2[i], dist2[i]+C, -1);
        cin >> board[i];
        for(int j=0;j<C;j++)
        {
            if(board[i][j] == 'J' )
            {
                Q2.push({i,j});
                dist2[i][j] = 0;
            }else if(board[i][j] == 'F')
            {
                Q1.push({i,j});
                dist1[i][j] = 0;
            }
        }
    }
    // 불의 BFS
    while(!Q1.empty())
    {
        auto cur = Q1.front(); Q1.pop();
        for(int dir=0;dir<4;dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx<0 || nx>=R || ny<0 || ny>=C) continue;
            if(dist1[nx][ny] != -1 || board[nx][ny] == '#') continue;
            dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
            Q1.push({nx, ny});
        }
    }
    // 지훈이의 BFS
    while(!Q2.empty())
    {
        auto cur = Q2.front(); Q2.pop();
        for(int dir=0;dir<4;dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx<0 || nx>=R || ny<0 || ny>=C){
                cout << dist2[cur.X][cur.Y] +1;
                return 0;
            }
            if(dist2[nx][ny] != -1 || board[nx][ny] != '.') continue;
            // dist1[]도 방문 해야하는지 검사 필요
            if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) continue;
            dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
            Q2.push({nx, ny});
        }
    }
    cout << "IMPOSSIBLE";
}

• 풀지못해서 답을 참고함
• BFS를 여러점에서 시작하는데 한쪽이 다른 한쪽에 영향을 주는 경우
  (서로 영향을 주는 경우는 이 방법 말고 백트래킹을 써야함;)

• 불의 BFS를 먼저 해서 예상 도착 거리를 dist1[][]에 구함

• 지훈이의 BFS를 할 때 아래 두 조건이 반드시 && 여야 한다
  1) 지훈이가 가려는 점이 불의 BFS 결과인 거리보다 작아야만 한다
  2) dist1[][]도 -1이 아니여야 한다(방문 한 점)

• 불의 경우 # 만 아니면 진행 하기 때문에 board[nx][ny] == '#'이면 continue
• 지훈이의 경우에는 '.' 일때만 가야 한다!

---

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

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
char board[1002][1002];
int R,C;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int,int>> J;
    queue<pair<int,int>> F;
    int ans=0;
    cin >> R >> C;
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++){
            cin >> board[i][j];
            if(board[i][j] == 'J') J.push({i,j});
            else if(board[i][j] == 'F') F.push({i,j});
        }
    while(!J.empty() || !F.empty())
    {
        ans++;
        queue<pair<int,int>> t2(F);
        for(int i=0;i<F.size();i++) F.pop();
        while(!t2.empty()){
            auto cur = t2.front(); t2.pop();
            for(int dir=0;dir<4;dir++){
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(ny <0 || nx < 0 || ny>=R || nx>=C) continue;
                if(board[ny][nx] == '#' || board[ny][nx] == 'F') continue;
                F.push({ny, nx});
                board[ny][nx] = 'F';
            }
        }

        queue<pair<int,int>> t(J);
        for(int i=0;i<J.size();i++) J.pop();
        while(!t.empty()){
            auto cur = t.front(); t.pop();
            for(int dir=0;dir<4;dir++){
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                /* 지훈이와 바로 붙은 벽 1칸으로는 탈출 못함 */
                if(ny <0 || nx < 0 || ny>=R || nx>=C){
                    cout << ans;
                    return 0;
                }
                if(board[ny][nx] == '.') {
                    J.push({ny, nx});
                    board[ny][nx] = 'J';
                }
            }
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}

• 2021.02.09 다시풀었을 때 지훈이와 바로 붙은 벽으로 탈출하지 못하는 조건때문에 막힘
  --> 바로 붙은 1칸인데 해당 행or열로 인식함...바보...
• 하나의 depth씩 불과 지훈이의 queue를 실행시켜서 해결함
• 하나의 depth씩 구현할 때 원본을 비우는 코드를 빼먹어서 무한루프에 빠졌음
• 불 --> 지훈 순서로 반드시 실행시켜야 함