백준 4179(불!) 풀이

문제

입력

출력

 

문제풀이

#include <iostream>
#include <queue>

using namespace std;

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

  int r, c;
  string a[1000];
  queue<pair<int, pair<int, int>>> q;
  pair<char,int> vis[1000][1000];
  int x[4] = {-1, 0, 1, 0};
  int y[4] = {0, -1, 0, 1};
  int min = 1000;

  cin >> r >> c;

  for (int i = 0; i < r; i++)
  {
    cin >> a[i];
  }

  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      if (a[i][j] == 'J' || a[i][j] == 'F')
      {
        q.push({1, {i, j}});
        vis[i][j] = {a[i][j], 1};
        while (!q.empty())
        {
          pair<int, pair<int, int>> tmp = q.front();
          q.pop();
          for (int k = 0; k < 4; k++)
          {
            int tmpx = tmp.second.first + x[k];
            int tmpy = tmp.second.second + y[k];
            int tmptime = tmp.first;

            if (tmpx < 0 || tmpy < 0 || tmpx > r - 1 || tmpy > c - 1)
            {
              continue;
            }

            if (a[tmpx][tmpy] == '#')
            {
              continue;
            }
            
            if (a[i][j] == 'F' && vis[tmpx][tmpy].first == 'F' && vis[tmpx][tmpy].second < tmptime + 1 || vis[tmpx][tmpy].first == 'J' && vis[tmpx][tmpy].second < tmptime + 1)
            {
              continue;
            }
            
            if (a[i][j] == 'J' && vis[tmpx][tmpy].first == 'J' || vis[tmpx][tmpy].first == 'F' && vis[tmpx][tmpy].second <= tmptime + 1)
            {
              continue;
            }

            vis[tmpx][tmpy] = {a[i][j], tmptime + 1};
            q.push({tmptime + 1, {tmpx, tmpy}});
          }
        }
      }
    }
  }

  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      if(i==r-1 || i == 0 || j==c-1 || j == 0){
        if(vis[i][j].first == 'J'){
          if(min > vis[i][j].second){
            min = vis[i][j].second;
          }
        }
      }
    }
  }

  if(min != 1000){
    cout<<min;
  }
  else{
    cout<<"IMPOSSIBLE";
  }
}

 

이 문제는 bfs로 해결할 수 있다.

 

처음에는 string형 배열로 입력을 받고 for문으로 시작점 J, F를 찾는다.

그 후 bfs를 실행한다.

 

bfs를 실행할 때 J는 F가 지나가는 길을 지나갈 수 없고 동시에 도착할 수도 없다.

즉 J는 F가 지나가기 전에 지나가야 한다는 말이다.

 

J가 먼저지났는지, F가 먼저 지났는지 알 수 있는 방법은

방문을 했을 떄 몇번쨰로 방문했는지 기록해주고 비교하면 된다.

그러기 위해 vis배열은 pair로 char형과 int형을 사용해주었다.

char는 누가 지나갔는지, int는 몇번째로 지나갔는지 표시해준다.

 

이렇게 해서 J가 먼저 밖으로 나갈 수 있으면  가장 빠른 탈출시간을 출력하고

나갈 수 없으면 IMPOSSIBLE을 출력한다.