[골드 3] 6087번: 레이저 통신

Original Source: https://www.acmicpc.net/problem/6087

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를 사용한다.
Queue에 위치와 방향, 거울의 개수를 저장한다.
방향이 변하면 거울을 한 개 놓아야 하므로, 이전의 방향과 다음의 방향이 다르면 거울 개수를 하나 증가시킨다.

BFS를 수행할 때 이전에 방문했던 칸이라도 그 칸의 거울 개수가 현재 거울의 개수보다 더 많거나, 혹은 같다면 다시 방문해야 한다.
다음 상황을 생각해보자.

C	.	.	.
.	*	*	.
.	.	.	.
*	*	*	.
*	*	*	C

위 상황에서, 이전에 방문한 칸을 다시 방문하지 않는다면 어떻게 될까? 왼쪽 → 아래쪽 → 오른쪽 → 위쪽 순으로 BFS를 수행한다고 가정했을 때 결과는 다음과 같다. 이때 숫자는 해당 칸까지 도달할 때 필요한 거울의 개수를 의미한다.

0	0	0	0
0	*	*	1
0	1	1	1
*	*	*	2
*	*	*	2

왼쪽 위 (0, 0)을 기준으로 첫 번째 좌표를 행, 두 번째 좌표를 열이라고 했을 때 (2, 3)에서 오류가 발생하는 것을 알 수 있다. 오류를 해결하려면 위에서 말했듯이 이전에 방문했던 칸의 거울 개수가 현재 거울 개수보다 같거나 많으면 다시 방문하도록 처리하면 된다.

위처럼 거울의 개수를 2차원 dist 배열에 저장하게 되는데, 이때 현재 칸의 거울의 개수를 dist 배열에서 확인하면 안 된다. BFS를 수행하면서 dist 배열 안의 숫자가 Override되기 때문이다. 따라서 Queue에 거울의 개수 정보를 넣어준 뒤 다시 Queue에서 거울 개수를 받아야 한다.

0	0	0	0
0	*	*	1
0	1	1	1
*	*	*	2 → 1
*	*	*	2 → 1

마지막으로 BFS를 수행하던 중 목표 칸에 도착했다고 해서 바로 BFS를 종료하면 안 된다. 바로 위의 표에서 목표 지점에 도달하자마자 종료했다면 정답으로 2가 출력되었을 것이다. 두 가지의 경로의 길이가 같지만 사용한 거울의 개수가 서로 다르기 때문에 발생한 결과다. 따라서 모든 경로를 고려하여 최적의 경로를 선택하기 위해 Queue가 빌 때까지 BFS를 전부 수행한 뒤 결과를 출력해야 한다.

내가 작성한 소스코드

#include <iostream>
#include <vector>
#include <queue>
#define WH 100
#define LEFT 0
#define UP 1
#define RIGHT 2
#define DOWN 3
#define NONE -1

using namespace std;

struct pos {
    int yy;
    int xx;
};

struct laser {
    pos p;
    int ddir;
    int ccnt;
};

int W, H;
char map[WH][WH];
// LEFT, UP, RIGHT, DOWN
int dy[4] = { 0, -1, 0, 1 };
int dx[4] = { -1, 0, 1, 0 };
vector<pos> Cpos;
int dist[WH][WH];

void init(void) {
    cin >> W >> H;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> map[i][j];

            if (map[i][j] == 'C') {
                Cpos.push_back({ i, j });
            }
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            dist[i][j] = -1;
        }
    }

    return;
}

void bfs(void) {
    int y = Cpos[0].yy;
    int x = Cpos[0].xx;
    int dir = NONE;
    int cnt = 0;
    
    queue<laser> q;
    q.push({ { y, x }, dir, cnt });
    dist[y][x] = 0;

    while (!q.empty()) {
        y = q.front().p.yy;
        x = q.front().p.xx;
        dir = q.front().ddir;
        cnt = q.front().ccnt;
        q.pop();

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

            if ((ny < 0 || ny > H - 1) || (nx < 0 || nx > W - 1)) {
                continue;
            }

             if (map[ny][nx] == '*') {
                continue;
            }

            if (dir == i || dir == NONE) {
                if (dist[ny][nx] == -1 || dist[ny][nx] >= cnt) {
                    q.push({ { ny, nx }, i, cnt });
                    dist[ny][nx] = cnt;
                }
            } else {
                if (dist[ny][nx] == -1 || dist[ny][nx] >= cnt + 1) {
                    q.push({ { ny, nx }, i, cnt + 1 });
                    dist[ny][nx] = cnt + 1;
                }
            }
        }
    }

    cout << dist[Cpos[1].yy][Cpos[1].xx];
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init();
    bfs();

    return 0;
}