[백준 c++] 6087 레이저 통신

문제

https://www.acmicpc.net/problem/6087
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

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

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

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

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

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

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

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

풀이

❌최단거리
👌🏻최소한의 방향전환

BFS + while문
벽을 만날 때까지 이동한다.
벽을 만날 때까지는 같은 가중치(방향전환 횟수)를 갖는다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int w, h;
char map[101][101];
int visited[101][101];
int d[101][101];
vector<pair<int, int>> c;
queue<pair<int, int>> q;

int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};

int main()
{
    cin >> w >> h;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            scanf("%1s", &map[i][j]);
            if (map[i][j] == 'C')
                c.push_back({i, j});
        }
    }

    int sy = c[0].first;
    int sx = c[0].second;
    q.push({sy, sx});

    visited[sy][sx] = 1;

    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            while (ny >= 0 && nx >= 0 && ny < h && nx < w && map[ny][nx] != '*')
            {
                if (!visited[ny][nx])
                {
                    visited[ny][nx] = 1;
                    q.push({ny, nx});
                    d[ny][nx] = d[y][x] + 1;
                }
                ny += dy[i];
                nx += dx[i];
            }
        }
    }

    cout << d[c[1].first][c[1].second] - 1;
}