문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 ‘C’로 표시되어 있는 칸이다.

‘C’로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울(‘/’, ‘')을 설치해서 방향을 90도 회전시킬 수 있다.

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

.: 빈 칸 *: 벽 C: 레이저로 연결해야 하는 칸 ‘C’는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

예제

예제 입력
7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

예제 출력
4
0
9

어제 포스팅에 이어 의도치 않게 오늘도 *이 나오는 바람에 강조 효과가 나타나버렸는데 양해를 부탁드립니다. 해결 방법을 아시는 분은 댓글로 알려주세요.. 바로 수정하겠습니다!

나의 접근 방법

  • 방향이 바뀔 때 마다 거울을 하나씩 사용하게 된다. 최대한 직선거리로 많이 움직인 다음에 방향을 꺾어야 최소로 거울을 사용하게 된다는 점을 고려하고 문제를 풀었다.

풀이

  • 우선 좌표와 방향, 사용한 거울 수를 저장하는 struct를 선언했다.
  • queue에 push를 해줄 때 방향 정보를 가지고 있기 때문에 이를 토대로 90도로 꺾었는지 아닌지를 판단했다.
  • 사용한 거울의 갯수를 저장하고 있는 배열을 통해 그 곳을 탐색할 것인지 말 것인지 결정했다. 다음에 탐색해야 할 부분에서 사용한 거울의 갯수가 queue의 front가 저장하고 있는 거울의 갯수보다 많거나 같다면 그 부분을 탐색하게 했다.
    • 처음에 클때만 탐색을 하게 했는데 틀렸다. 크거나 같은 경우라는 것을 명심하자. (사용한 거울 수는 같은데 다른 경로가 존재할 수 있기 때문이다.)

코드

//todo : BFS를 실행하되 방향을 체크하면서 방향이 달라질 경우 거울 횟수 + 1
//목표 C 지점에 도착했을 때 거울 갯수 체크하고 최소값으로 계속 초기화
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
using namespace std;

int W, H, d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

vector<pair<int, int>> C_loc;
char map[101][101];
int use_mirror[101][101] = {0, };
struct data{
  int y;
  int x;
  int dir;
  int mirror;
};

bool check(int y, int x)
{
  return (y>=0 && y<H && x>=0 && x<W);
}
void input()
{
  cin>>W>>H;
  for(int i = 0 ; i<H ; i++)
  {
    for(int j = 0 ; j<W ; j++)
    {
      use_mirror[i][j] = 100000;
      cin>>map[i][j];
      if(map[i][j] == 'C') C_loc.push_back({i,j});
    }
  }
}
void doBFS()
{
  deque<struct data> dq;
  dq.push_back({C_loc[0].first, C_loc[0].second, -1, 0});
  use_mirror[C_loc[0].first][C_loc[0].second] = 0;
  while(!dq.empty())
  {
    struct data t = dq.front();
    dq.pop_front();
    for(int i = 0 ; i<4 ; i++)
    {
      int nextY = t.y + d[i][0], nextX = t.x + d[i][1];

      if(check(nextY, nextX) && map[nextY][nextX] != '\*')
      {
        if(t.dir == i || t.dir == -1)
        {
          if(t.mirror <= use_mirror[nextY][nextX])
          {
            dq.push_front({nextY, nextX, i, t.mirror});
            use_mirror[nextY][nextX] = t.mirror;
          }
        }
        else
        {
          if(t.mirror + 1 <= use_mirror[nextY][nextX])
          {
            dq.push_back({nextY, nextX, i, t.mirror + 1});
            use_mirror[nextY][nextX] = t.mirror + 1;
          }
        }
      }
    }
  }
}
int main(void)
{
  input();
  doBFS();
  cout<<use_mirror[C_loc[1].first][C_loc[1].second];
  return 0;
}

비슷하다고 생각한 문제

  • 프로그래머스의 경주로건설이라는 문제가 이 문제와 비슷하다. 비슷한 유형의 문제를 풀어보고 싶다면 풀어보도록 하자.