[백준/C++] 6087번 레이저 통신

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

6087번: 레이저 통신

기본적인 bfs문제에 약간의 테크닉을 요구하는 문제이다.

우선 C가 두개 주어지므로 그냥 먼저 나오는 C를 시작점이라고 치고, 늦게 나오는 C를 도착점이라 친다.

그리고 시작점을 큐에 넣고 bfs를 시작하는데, 큐의 맨 앞에 것을 가져와서 4가지 방향을 탐색하는 건 기존 bfs와 동일하다.

그러나 여기서 레이저의 특징을 이용해야한다!

레이저는 한 방향으로만 직진하므로, while문을 통해 주어진 범위 안에 존재하거나 벽을 만나지 않을 때 까지 직진해줘야한다.

아직 방문하지 않은 곳을 만나면 현재 x,y의 count값에서 +1한 값을 저장해준다

ex) C 빈칸 빈칸 빈칸 벽 인 경우, C에서 오른쪽으로 레이저가 진행한다고 하면 count배열 값은

count: [0] [1] [1] [1] [0] 이 된다.

그리고 해당 빈칸의 좌표를 큐에 넣어준다.

​

이렇게 되면, 특정 좌표에 도달하기까지 필요한 mirror의 개수는, 직선의 개수 -1 (=배열의 값 -1) 이 된다.

-1인 이유는 처음 출발할 땐 거울이 필요하지 않지만 +1 해주었기 때문!

우상단 C(x,y)에서 출발하여 1번 화살표에 걸리는 곳(nx,ny)은 값이 1로 채워지고,

C 왼쪽의 좌표(x,y)에서 아래로 향하는 2번 화살표에 걸리는 곳(nx,ny)은 값이 2로 채워지고

2번 화살표의 마지막 점(x,y)에서 왼쪽으로 향하는 3번 화살표에 걸리는 곳(nx,ny)은 값이 3으로 채워지고

도착지 C 밑에 있는 점(x,y)에서 위쪽으로 향하는 4번 화살표에 걸리는 곳(nx,ny)은 값이 4으로 채워진다!

​

즉, 출발 C에서 도착 C로 향하는데 필요한 직선의 개수 -1이 거울의 개수이다!

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

queue<pair<int,int>> q;
int w,h;
char map[101][101];
int count_for_change_dir[101][101];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
pair<int,int> start,End;

void bfs() {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 범위 안에 들고, 벽이 아닌 경우
            while (nx >= 0 && nx < h && ny >= 0 && ny < w && map[nx][ny] != '*') {
                if (count_for_change_dir[nx][ny] == 0) {
                    count_for_change_dir[nx][ny] = count_for_change_dir[x][y] + 1;
                    q.push({nx, ny});
                }
                // 레이저의 특성 : 한 방향으로 쭉 이동
                nx += dx[i];
                ny += dy[i];
            }
        }
    }
}

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

    cin >> w >> h;
    int ccnt=0;
    for(int i=0; i<h ;i++){
        for(int j=0; j<w; j++){
            cin >> map[i][j];
            if(map[i][j]=='C'){
                if(ccnt==0){
                    start.first=i;
                    start.second=j;
                    ccnt++;
                }
                else{
                    End.first=i;
                    End.second=j;
                }
            }
        }
    }
    q.push({start.first,start.second});
    bfs();
    // while문에서 한 방향으로 '처음' 나아갈 때도 거울의 수를 +1 해주었기 때문에 -1
    cout << count_for_change_dir[End.first][End.second] - 1 << endl;
    return 0;
}