[백준] 6087번 레이저 통신

6087 레이저 통신

문제

---

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

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

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

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

입력

---

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

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

.: 빈 

*: 벽 

C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

---

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

---

풀이)

3차원 방문 표시 배열을 이용해서 푼 문제이다.

int visited[i][j][dir]; // (i,j) 위치를 dir방향으로 왔을 때, 설치했던 거울 개수의 최솟값

visited[][][]의 초기값은 절대 나올 수 없는 최고값인 999999999로 두었다.

위를 이용한 과정은 이러하다.

1. 시작점과 도착점 위치를 저장해 놓는다. 

2. BFS를 통해 시작점부터 도착점까지 탐색한다.

 2.1 출발지의 visited[][][0~3]는 모두 0으로 초기화한다. 처음 출발할 때는 거울 없이 4방향으로 모두 탐색할 수 있으므로

 2.2 queue에서 정보를 꺼낼 때마다, 레이저의 방향을 총 3가지 방향으로 바꿔서 탐색.

     ① 원래 왔던 방향 

     ② 현재 구역에 '\'거울이 설치되어서 수직으로 바뀌는 방향

     ③ 현재 구역에 '/'거울이 설치되어서 수직으로 바뀌는 방향

    

     상하좌우를 0123이라고 할때

     int change_dir[4][3] = { {0,2,3},{1,2,3},{2,0,1},{3,0,1} }; 을 선언해 각 방향에서 3가지 방향으로 어떻게 바뀌는지 저장해놨다.

     => change_dir[0][0~2] : 원래 왔던 방향이 0 즉 위쪽방향이었으면, 바뀌는 방향은 0 위쪽방향, 2 왼쪽방향, 3 오른쪽방향.

    change_dir[2][0~2] : 원래 왔던 방향이 2 즉 왼쪽방향이었으면, 바뀌는 방향은 2 왼쪽방향, 0 위쪽방향, 1 아래쪽방향.

 2.3 만약, 이전에 방문했던 거울 설치 개수 값이 현재 방문했을 때의 거울 설치 개수 값보다 작으면 현재 탐색은 pass해서

      탐색 시간을 줄인다.

3. 탐색을 마친 후, 도착점의 visited[][][0~3]의 값을 확인해 그 중 가장 작은 값을 출력한다.

    (도착점에 어느 방향으로 왔을 때가 가장 적은 거울 설치 개수로 왔는지 모르니깐 4방향 모두 확인)

코드)

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
 
#define INF 999999999
int W, H;
char map[100][100];
pair<int, int> start = { -1,-1 }, des = {-1,-1};//출발지 도착지
int visited[100][100][4];
 
//상,하,좌,우 : 원래방향 1개 + 거울로 인해 바뀐 방향 2개
int change_dir[4][3] = { {0,2,3},{1,2,3},{2,0,1},{3,0,1} };
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
struct Info {
    int y, x, dir, cnt;//위치, 방향, 거울개수
    Info() {
        y = 0;
        x = 0;
        dir = 0;
        cnt = 0;
    }
    Info(int y, int x, int dir, int cnt) {
        this->y = y;
        this->x = x;
        this->dir = dir;
        this->cnt = cnt;
    }
};
void bfs() {
    queue<Info> qu;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            for (int k = 0; k < 4; k++) {
                visited[i][j][k] = INF;
            }
        }     
    }
    for (int i = 0; i < 4; i++) {
        visited[start.first][start.second][i] = 0;
        qu.push({ start.first,start.second,i,0 });
    }
    while (!qu.empty())
    {
        int y = qu.front().y;
        int x = qu.front().x;
        int dir = qu.front().dir;
        int cnt = qu.front().cnt;
        qu.pop();
        if (visited[y][x][dir] < cnt) continue;
        for (int i = 0; i < 3; i++) {
            int ndir = change_dir[dir][i];
            int ny = y + dy[ndir];
            int nx = x + dx[ndir];
            int ncnt = cnt;
            if (ny < 0 || ny >= H || nx < 0 || nx >= W || map[ny][nx] == '*')continue;
            if(i > 0)ncnt++; //거울설치
            if (visited[ny][nx][ndir] <= ncnt) continue;
            visited[ny][nx][ndir] = ncnt;
            if (map[ny][nx] == 'C') {
                continue;
            }
            qu.push({ ny,nx,ndir,ncnt });
        }
        
 
    }
    
}
int main() {
    scanf("%d %d", &W, &H);
    getchar();
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            map[i][j] = getchar();
            if (map[i][j] == 'C') {
                if (start.first == -1)start = { i,j };
                else des = { i,j };
            }
        }
        getchar();
    }
    bfs();
    int result = 999999999;
    for (int i = 0; i < 4; i++) {
        if (result > visited[des.first][des.second][i]) result = visited[des.first][des.second][i];
    }
    printf("%d", result);
    return 0;
}