[BOJ/Gold 3] 백준 6087 레이저 통신(C++)

문제 링크

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를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

예제 입력 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

예제 출력 1

3

알고리즘 분류

• 그래프 탐색

풀이

BFS를 통해서 C에서 C로 가는 길을 찾으면서, 해당 칸까지 이동했을 때 방향이 몇 번을 꺾였는지 기록한다.

(Y, X)칸까지 이동했을 때 필요한 거울의 개수를 기록하기 위해 Mirror[100][100] 변수를 선언한다.

여기서 해당 칸까지 어떤 방향으로 이동했는지까지 따지기 위해 2차원이 아닌 3차원 배열로써 Mirror[100][100][4]를 선언한다. 그리고 미리 배열의 각 원소의 값을 10^9로 초기화해준다.

또한 해당 칸을 특정 방향을 통해 방문했다는 3차원 배열 또한 선언해준다.

이제 첫 번째 C, 즉 C1부터 출발해서 BFS를 통해 이동한다. 여기서 큐를 선언하는데, 필요한 변수는 Y, X좌표, 거울의 개수, 방향 총 4가지이다.

이동하면서 현재 방향과 다른 방향으로 이동한다면 거울의 개수를 1개 추가한다. 그리고 다음 칸까지 필요한 거울의 개수가 최솟값일 경우에만 이동한다.

마지막으로 4방향을 통해서 두 번째 C, 즉 C2까지 도달했을 때 필요한 거울의 개수 Mirror[C2.Y][C2.X][0]부터  Mirror[C2.Y][C2.X][3]까지 중 최솟값을 구한다. 특정 방향을 통해서 방문하지 않았다면 따지지 않는다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 101
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int W, H;
int MAP[MAX][MAX];
queue<pair<pair<int, int>, pair<int, int> > > Q;
int Mirror[MAX][MAX][4];
bool Visited[MAX][MAX][4];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int A, B;
int Answer = INF;

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < 4; k++) {
                Mirror[i][j][k] = INF;
            }
        }
    }
}

void input() {
    cin >> W >> H;
    for (int i = 1; i <= H; i++) {
        string S;
        cin >> S;
        for (int j = 1; j <= W; j++) {
            if (S[j - 1] == '*') {
                MAP[i][j] = -1;
            }
            else if (S[j - 1] == 'C') {
                if (Q.empty()) {
                    Q.push(make_pair(make_pair(i, j), make_pair(0, -1)));
                    for (int k = 0; k < 4; k++) {
                        Mirror[i][j][k] = 0;
                        Visited[i][j][k] = true;
                    }
                }
                else {
                    MAP[i][j] = 1;
                    A = i;
                    B = j;
                }
            }
        }
    }
}

void settings() {
    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowM = Q.front().second.first;
        int NowD = Q.front().second.second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 1) && (NextY <= H) && (NextX >= 1) && (NextX <= W) && (MAP[NextY][NextX] != -1)) {
                if (NowD == -1) {
                    if (Mirror[NextY][NextX][i] > NowM) {
                        Visited[NextY][NextX][i] = true;
                        Mirror[NextY][NextX][i] = NowM;
                        Q.push(make_pair(make_pair(NextY, NextX), make_pair(NowM, i)));
                    }
                }
                else {
                    if (NowD != i) {
                        if (Mirror[NextY][NextX][i] > NowM + 1) {
                            Visited[NextY][NextX][i] = true;
                            Mirror[NextY][NextX][i] = NowM + 1;
                            Q.push(make_pair(make_pair(NextY, NextX), make_pair(NowM + 1, i)));
                        }
                    }
                    else {
                        if (Mirror[NextY][NextX][i] > NowM) {
                            Visited[NextY][NextX][i] = true;
                            Mirror[NextY][NextX][i] = NowM;
                            Q.push(make_pair(make_pair(NextY, NextX), make_pair(NowM, i)));
                        }
                    }
                }
            }
        }
    };

    for (int i = 0; i < 4; i++) {
        if (Visited[A][B][i]) {
            Answer = min(Answer, Mirror[A][B][i]);
        }
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}