[백준 3197] 백조의 호수

www.acmicpc.net/problem/3197

3197번: 백조의 호수

골1이라 그런 것인가 어렵다... bfs이긴 하나 큐를 3개 활용해야 하는 문제였다.

5번만에 겨우 성공했는데 틀렸던 포인트에 대해서 짚고 넘어가고자 한다.

 

1. 얼음이 녹는 것

얼음은 물이 맞닿아 있는 지점만 녹는다. 처음 인풋을 받으면서 물에 대해서만 푸쉬한다.

bfs를 돌릴때 큐에 푸쉬되는 조건은 물에 상하좌우에 위치한 얼음이라는 점이다.

주의할 점은 큐의 종료조건이다. bfs는 깊이 탐색이기 때문에 while(!q.empty())로 설정하면 하루만에 얼음이 다 녹아버린다. 날마다 차례대로 얼음이 녹아야 하므로 int size = q.size(); while(size--)를 해주자.

 

2. 백조의 움직임

여기서 자꾸 틀렸는데 visited배열을 초기화하고 매번 새로 bfs를 실시하면 tle가 발생한다. 따라서 nextQ를 새로 만들어서 백조가 갈 다음 패스를 푸쉬해둔다. 

해당 라운드에서 백조가 갈 수 있는 곳은 물(.)로 다음 배열이 .이면 현재 큐에 푸쉬한다. 

하지만 얼음(X)라면 다음 라운드에 갈 곳이므로 nextQ에 푸쉬해둔다.

현재 라운드를 다 돌고 나면 (=갈 수 있는 .을 모두 방문했다면) q에 nextQ를 넣어둔다. 이때 nextQ는 매번 초기화해야 한다. 

 

#include <stdio.h>
#include <queue>

using namespace std;

int r, c;
int dst_r, dst_c;
char lake[1500][1500];
int visited[1500][1500];

int drow[4] = {0, 0, 1, -1};
int dcol[4] = {1, -1, 0, 0};

struct S
{
  int row, col;
};

queue<S> swan;
queue<S> ice;


bool moveSwan()
{
  queue<S> nextQ; // 다음날에 갈 곳
  while (!swan.empty())
  {
    S cur = swan.front();

    if (cur.row == dst_r && cur.col == dst_c)
    {
      return true;
    }
    swan.pop();

    for (int i = 0; i < 4; i++)
    {
      int nr = cur.row + drow[i];
      int nc = cur.col + dcol[i];

      if (nr < 0 || nc < 0 || nr > r - 1 || nc > c - 1 || visited[nr][nc])
      {
        continue;
      }

      if (lake[nr][nc] == '.')
      {
        swan.push({nr, nc}); //오늘 갈 곳들
      }
      else
      {
        nextQ.push({nr, nc}); //tle를 방지하기 위해 다음날에 갈 곳을 미리 저장해두자.
      }
      visited[nr][nc] = 1;
    }
  }

  swan = nextQ;

  return false;
}

void water()
{
  int iceSize = (int)ice.size();

  while (iceSize--)
  {
    S cur = ice.front();
    ice.pop();

    for (int i = 0; i < 4; i++)
    {

      int nr = cur.row + drow[i];
      int nc = cur.col + dcol[i];

      if (nr < 0 || nc < 0 || nr > r - 1 || nc > c - 1)
      {
        continue;
      }

      if (lake[nr][nc] == 'X')
      {
        ice.push({nr, nc});
        lake[nr][nc] = '.'; //얼음이 녹았음을 표시
      }
    }
  }
}

int main(void)
{
  scanf("%d %d", &r, &c);

  for (int i = 0; i < r; i++)
  {
    scanf("%s", lake[i]);
    for (int j = 0; j < c; j++)
    {
      if (lake[i][j] == 'L')
      {
        if (swan.size() == 0)
        {
          swan.push({i, j});
          visited[i][j] = 1;
        }
        else
        {
          dst_r = i;
          dst_c = j;
        }

        lake[i][j] = '.';
      }

      if (lake[i][j] == '.')
      {
        ice.push({i, j});
      }
    }
  }

  int day = 0;

  while (1)
  {
    if (moveSwan())
    {
      break;
    }

    water();
    day++;
  }

  printf("%d\n", day);

  return 0;
}