문제

  • 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.

입력

  • 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

각 R줄 동안 C만큼의 문자열이 주어진다.

’.’은 물 공간, ‘X’는 빙판 공간, ‘L’은 백조가 있는 공간으로 나타낸다.

출력

  • 첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

예제

예제 입력
8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

예제 출력
2

접근

  • 1일차 : 일반적인 BFS로 처음에 접근했다. -> 실패했다.
  • 2일차 : 이분탐색을 활용하여 접근했다. -> 실패했다.(솔직히 이걸로 통과할 줄 알았는데…ㅠ)
    • 각각의 얼음(X)에서 BFS를 실행하면 그 얼음이 며칠째에 녹는지 알 수 있다. 따라서 빙하들이 녹는 날짜를 표기한 후 이분탐색으로 시간을 줄여보려 하였으나 실패!
  • 3일차 : 앞으로 탐색해야 할 곳과 앞으로 녹을 얼음의 정보를 미리 Queue에 저장하는 방법 -> 성공

내가 생각한 풀이

  • 녹은 지점의 주변의 얼음만 변한다 -> 미리 녹을 얼음을 알 수 있다.
  • 기존에 탐색했던 부분은 탐색할 필요 없이 새롭게 녹은 부분에 대해서만 탐색을 이어 나가면 된다. -> n일차에 만나지 못하면 n-1일차에도 만나지 못하는 것이므로.

미처 생각하지 못했던것

  • 백조 두 마리의 위치를 찾을 때 flag 라는 bool 변수를 사용했는데 0일때와 1일때로 구분을 했어야 했다. 근데 이걸 깜빡해서 1시간인가 2시간동안 헤맸다…
    • 디테일에 더 신경쓸 것!
  • n일차에는 n-1일차에 탐색한 곳을 다시 탐색할 필요가 없다는 점.
    • 멍청하게 얼음을 녹이고 처음 위치에서 부터 BFS를 실행했다. Map의 크기가 1500 * 1500인데 당연히 시간, 메모리 초과가 날 수 밖에 없었다…

코드

#include<iostream>
#include<queue>
using namespace std;

int R, C, d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}, r = 0;

char map[1501][1501];
bool check[1501][1501] = {0, }, result_flag = 0;
pair<int, int> swan1, swan2;
queue<pair<int, int>> Q, WQ;
bool check_bound(int y, int x)
{
  return (y>=0 && y<R && x>=0 && x<C);
}
void input()
{
  cin>>R>>C;
  bool flag = 0;
  for(int i = 0 ; i<R ; i++)
  {
    for(int j = 0 ; j<C ; j++)
    {
      cin>>map[i][j];
      if(map[i][j] == 'L')
      {
        if(flag == 0)
        {
          swan1.first = i;
          swan1.second = j;
          flag = 1; //어처구니 없이 빼먹어서 고생했던 부분. 디테일에 신경쓰자.
        }
        else
        {
          swan2.first = i;
          swan2.second = j;
        }
        WQ.push({i,j});
      }
      else if(map[i][j] == '.')
        WQ.push({i,j});
    }
  }
}
void search()
{
  queue<pair<int, int>> NQ;

  check[swan1.first][swan1.second] = 1;
  while(!Q.empty())
  {
    pair<int, int> t = Q.front();
    Q.pop();
    if(t.first == swan2.first && t.second == swan2.second) //두 번째 백조가 있는 곳에 도달하면 break
    {
      result_flag = 1;
      break;
    }
    for(int i = 0 ; i<4 ; i++)
    {
      int nextY = t.first + d[i][0], nextX = t.second + d[i][1];
      if(!check_bound(nextY, nextX) || check[nextY][nextX] == 1) continue;
      check[nextY][nextX] = 1; //.이던 X이던 그 지점에 대한 정보를 Queue에 넣었기 때문에 visit check를 해준다.
      if(map[nextY][nextX] == '.' || map[nextY][nextX] == 'L')
      {
        Q.push({nextY, nextX});
      }
      else if(map[nextY][nextX] == 'X') //X라면 물과 맞닿아 있기 때문에 다음에 탐색할 지점이다.
      {
        NQ.push({nextY, nextX});
      }
    }
  }
  Q = NQ;
}
void changeMap()
{
  int q_size = WQ.size();
  while(q_size--)
  {
    pair<int, int> t = WQ.front();
    WQ.pop();
    for(int i = 0 ; i<4 ; i++)
    {
      int nextY = t.first + d[i][0], nextX = t.second + d[i][1];
      if(!check_bound(nextY, nextX)) continue;
      if(map[nextY][nextX] == 'X')
      {
        map[nextY][nextX] = '.';
        WQ.push({nextY, nextX}); //변화가 일어난 지점에서만 또다른 변화가 일어나기 때문에 그 지점을 미리 알아놓는다.
      }
    }
  }
}
int main(void)
{
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  input();
  Q.push(swan1);
  while(1)
  {
    search();
    if(result_flag == 1)
    {
      cout<<r;
      break;
    }
    changeMap();
    r++;
  }
  return 0;
}