[ 백준 BOJ ] 2151번 - 거울 설치 (C++)

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

생각 흐름

• 거울을 대각선으로만 설치할 수 있으므로 빛이 쏴졌을 때 이동할 경로는 상, 하, 좌, 우 밖에 없다. 즉, 빛이 쏘아진 방향에서 좌, 우로만 이동이 가능하다.
• 이 때 빛이 a,b 지점을 지났다고 했을 때 ➡️ 이렇게 쏴졌을 때랑 ⬆️ 이렇게 쏴졌을 때랑 빛이 이동하는 방향이 아예 달라지므로 방향을 따져가며 방문 체크를 해야 된다. 그렇게 [y][x][dir] 형태의 checked 배열을 만들었다.
• 결국 최단 경로 문제이기에 bfs 알고리즘을 사용해서 풀었다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N;
vector<string> input;

//cnt, directer(상0,하1,죄2,우3), y, x
queue<pair<pair<int,int>,pair<int,int>>> q;
//y, x, directer
bool checked[50][50][4];

int bfs(int y, int x, int dir){
    q.push({{0,dir},{y,x}});
    for(int i = 0; i<4; i++){
        checked[y][x][i]=true;
    }
    while(!q.empty()){
        int cnt = q.front().first.first;
        int dir = q.front().first.second;
        int y = q.front().second.first;
        int x = q.front().second.second;

        q.pop();
        
        if(dir == 0){
            int my = y;
            while(true){
                my--;
                if(my<0) break;
                if(input[my][x]=='*') break;
                if(checked[my][x][0]) continue;
                if(input[my][x]=='#') return cnt;
                if(input[my][x]=='!'){
                    checked[my][x][0] = true;
                    q.push({{cnt+1, 2},{my, x}});
                    q.push({{cnt+1, 3},{my, x}});
                }
            }
        }else if(dir == 1){
            int my = y;
            while(true){
                my++;
                if(my>N-1) break;
                if(input[my][x]=='*') break;
                if(checked[my][x][1]) continue;
                if(input[my][x]=='#') return cnt;
                if(input[my][x]=='!'){
                    checked[my][x][1] = true;
                    q.push({{cnt+1, 2},{my, x}});
                    q.push({{cnt+1, 3},{my, x}});
                }
            }
            
        }else if(dir ==2){
            int mx = x;
            while(true){
                mx++;
                if(mx>N-1) break;
                if(input[y][mx]=='*') break;
                if(checked[y][mx][2]) continue;
                if(input[y][mx]=='#') return cnt;
                if(input[y][mx]=='!'){
                    checked[y][mx][2] = true;
                    q.push({{cnt+1, 0},{y, mx}});
                    q.push({{cnt+1, 1},{y, mx}});
                }
            }
        }else{
            int mx = x;
            while(true){
                mx--;
                if(mx<0) break;
                if(input[y][mx]=='*') break;
                if(checked[y][mx][3]) continue;
                if(input[y][mx]=='#') return cnt;
                if(input[y][mx]=='!'){
                    checked[y][mx][3] = true;
                    q.push({{cnt+1, 0},{y, mx}});
                    q.push({{cnt+1, 1},{y, mx}});
                }
            }
        }
    }
    
    return 987654321;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    int doorY=-1, doorX=-1;
    for(int i = 0; i<N; i++){
        string tmp;
        cin>>tmp;
        
        input.push_back(tmp);
        
        for(int j = 0; j<N; j++){
            if(tmp[j]=='#'){
                doorY = i;
                doorX = j;
            }
        }
    }
    
    int answer = 987654321;
    for(int i = 0; i<4; i++){
        answer = min(answer, bfs(doorY, doorX, i));
    }
    
    cout<<answer<<endl;
    
    return 0;
}