레이저 통신

Problem link: https://www.acmicpc.net/problem/6087

BFS 아이디어를 잘 응용하면 쉽게 풀어 줄 수 있다.

BFS의 장점은 간선에 가중치가 없는 그래프라면 곧 방문순서가 경로의 길이가 된다는 점이다.

다시 말하면, 간선에 가중치가 없으므로 BFS 순서에 따라 정점을 방문하다가 최초로 목적지 정점을 탐색하게 되는 순간이 곧 최단 경로이다.

위의 성질을 마음에 새기고, 본 문제의 풀이를 기술하면 아래와 같다.

• 시작 정점을 큐에 넣는다(자명하게 시작정점은 거울 0개로 도달 가능하다).
• 시작 정점은 거울을 설치하지 않아도 사방으로 빛을 보내줄 수 있으므로 시작 정점으로부터 뻗어나가는 4방향에 위치하는 정점들은 모두 거울 0개로 도달 가능하다(벽을 만나기 전까지는).
• 따라서, 시작 정점에서 뻗어나가는 4방향에 위치하는 정점들을 모두 큐에 넣어준다.
• 이제 BFS를 시작한다.
• BFS에서 Pop된 정점이 도착 정점이라면, 그 정점의 방문 순서(VISIT에 기록된)이 곧 거울의 수와 같다.
• BFS에서 Pop된 정점이 도착 정점이 아니라면, 해당 정점에서 다시 탐색을 진행해주면 된다.
• 해당 정점을 기준으로 4방향으로 뻗어나가는 방향의 정점들에 대해서, 아직 방문하지 않은 정점들이 있다면, VISIT에 1을 더하여 큐에 넣어준다.
  • 매번 인접 정점을 큐에 넣는 작업을 수행할 때 4방향으로 뻗어나가는 모든 정점을 큐에 넣어주므로 인접한 정점이 방문되지 않았다면 반드시 거울이 있어야만 된다.
  • 거울 없이 갈 수 있는 곳이었다면 이미 방문되었으리라

#include <cstdio>
#include <utility>
#include <queue>
#include <vector>

using namespace std;

const int kMaxW = 100;
const int kMaxH = 100;

vector<pair<int, int> > LASERS;
int W;
int H;
int VISIT[kMaxH][kMaxW];
char BOARD[kMaxH][kMaxW];
queue<pair<int, int> > Q;

const int dr[4] = { -1, 0, 1, 0 };
const int dc[4] = { 0, 1, 0, -1 };

void Span(const int row, const int col, const int dir, const int cost)
{
  int nrow = row;
  int ncol = col;

  while (true)
  {
    nrow += dr[dir];
    ncol += dc[dir];

    if (0 > nrow || nrow >= H || 0 > ncol || ncol >= W || BOARD[nrow][ncol] == '*')
    {
      break;
    }

    if (VISIT[nrow][ncol] == -1)
    {
      VISIT[nrow][ncol] = cost;
      Q.emplace(nrow, ncol);
    }
  }
}

int Solve(void)
{
  VISIT[LASERS[0].first][LASERS[0].second] = 0;
  Q.push(LASERS[0]);
  for (int dir = 0; dir < 4; ++dir)
  {
    Span(LASERS[0].first, LASERS[0].second, dir, 0);
  }

  while (!Q.empty())
  {
    int row = Q.front().first;
    int col = Q.front().second;
    Q.pop();

    if (row == LASERS[1].first && col == LASERS[1].second)
    {
      return VISIT[row][col];
    }

    for (int dir = 0; dir < 4; ++dir)
    {
      Span(row, col, dir, VISIT[row][col] + 1);
    }
  }

  return -1;
}

int main(void)
{
  // Read Input
  scanf(" %d %d", &W, &H);
  for (int row = 0; row < H; ++row)
  {
    for (int col = 0; col < W; ++col)
    {
      scanf(" %c", &BOARD[row][col]);

      if (BOARD[row][col] == 'C')
      {
        LASERS.emplace_back(row, col);
      }

      VISIT[row][col] = -1;
    }
  }

  // Solve
  printf("%d\n", Solve());

  return 0;
}