[백준] 레이저 통신

전 포스팅에서 경주로 건설을 먼저 풀었던 이유는 사실 이 문제를 푸는데 좀 더 개념이 잡히고 도전 해보고 싶었다. 시뮬레이션 골드 3이상 문제들은 솔직히 좀 생각도 많이 해야하고 난이도가 있는 느낌이다.

C 라는곳에서 레이저를 발사하고 다른 C에 그 레이저가 전달 되야 하는게 문제의 목표이다. 레이저는 해당 방향으로 일자로만 갈 수 있지만 거울을 설치해서 방향을 바꿀 수 있고 다른 C로 레이저가 닿을때까지 최소한의 거울만 써야 하는게 핵심이다.

경주로 건설 문제와 마찬가지로, 이 문제는 다른 C로 도달만 하면 끝나는 문제가 아니고 다른 C에 닿아도 가는 경로에 얼마나 많은 거울이 사용됐는지를 알아야한다. 그렇기 때문에 BFS 로 탐색을 하더라도 목표 좌표에서 계속 최소 값을 갱신 시켜줘야 한다.

경주로 건설과 정말 비슷한 접근으로 문제를 풀어 볼려고 했는데 시간초과가 났었다. 높은 이유로 queue 가 너무 많이 쌓였던거 같다. 3차원 방문 벡터로 하게 될경우 좀 더 디테일하게 접근할 수 있는 장점이 있지만 일반 방문배열보다 더 많은 정보를 큐에 넣게 된다.

이 문제는 최소한의 거울을 가지고 있어야하고 내가 느낀 결론은 사실 방향까지는 크게 중요하지 않다고 생각했다. 앞서 풀었던 경주로 건설 문제는 어느 방향에 따라서 값이 추가되는게 달라지기 때문에 방향성이 중요하다 생각했는데 이런 문제는 그냥 2차원 방문 배열로도 충분히 풀 수 있었다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, M; 
char matrix[101][101]; 
//int visited[101][101][4]; 
int visited[101][101];
int answer = INT_MAX; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 
vector<pair<int,int>> points; 

struct Laser{
    int x, y, dir, mirror; 
};

void Input(){
    cin >> M >> N; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            char c; 
            cin >> c; 
            matrix[i][j] = c; 
            if(c == 'C') points.push_back({i,j}); 
        }
    }
}

void Solution(){
    memset(visited,987654,sizeof(visited)); 
    queue<Laser> q; 
    q.push({points[0].first,points[0].second,-1,0}); 
    //for(int i = 0; i < 4; i++) visited[points[0].first][points[0].second][i] = 0; 
    visited[points[0].first][points[0].second] = 0; 
    while(!q.empty()){
        int size = q.size(); 
        for(int i = 0; i < size; i++){
            Laser laser = q.front();
            q.pop(); 
            int x = laser.x, y = laser.y, curr_dir = laser.dir, mirr = laser.mirror; 
            
            //cout << x << ' ' << y << ' ' << curr_dir << ' ' << mirr << ' ' << endl; 
            if(x == points[1].first && y == points[1].second){
                answer = min(answer,mirr); 
                continue; 
            }

            for(int d = 0; d < 4; d++){
                int nX = x + dir[d].first; 
                int nY = y + dir[d].second; 
                int nD = d; 

                if(nX < 0 || nX >= N || nY < 0 || nY >= M || matrix[nX][nY] == '*') continue; 

                if(curr_dir == -1 || curr_dir == nD){
                    if(visited[nX][nY]>= mirr){
                        visited[nX][nY] = mirr; 
                        q.push({nX,nY,nD,mirr}); 
                    }
                    // if(visited[nX][nY][nD] >= mirr){
                    //     visited[nX][nY][nD] = mirr; 
                    //     q.push({nX,nY,nD,mirr}); 
                    // }
                }

                else if(curr_dir != d){
                    if(visited[nX][nY]>= mirr + 1){
                        visited[nX][nY] = mirr + 1; 
                        q.push({nX,nY,nD,mirr+1}); 
                    }
                    // if(visited[nX][nY][nD] >= mirr + 1){
                    //     visited[nX][nY][nD] = mirr + 1; 
                    //     q.push({nX,nY,nD,mirr+1}); 
                    // }
                }

            }
        }
    }

    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

솔직히 특정 좌표로만 가야하는 문제는 이해 했는데, 아직 완벽하게 이런 모든 조합을 비교해야 하는 BFS 탐색 문제에 3차원 VS 2차원 배열의 차이를 이해하지는 못했다.

다만 이런 비슷한 문제가 나온다면 난 아마 3차원을 먼저 사용해보고 그리고 2차원을 쓸거같다.

배운점:
1. 3차원 방문 배열 VS 2차원 방문 배열
3. BFS 의 활용