[백준] 2151번 거울 설치

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define MAX 50
#define INF 987654321

using namespace std;
typedef struct{
    int x,y,Dir;
}Pos;

int N, Answer;
char MAP[MAX][MAX];
int Visit[MAX][MAX][4];
int dx[]={0,0,1,-1}; // 오,왼,위,아래
int dy[]={1,-1,0,0};
pair<int,int> Start,End; //출발, 도착 좌표
queue<Pos> Q;

void Input(){ //맵 입력받기
    int Tmp=0; // # 출구 입구 구분 용도
    cin>>N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>MAP[i][j];
            if(MAP[i][j] =='#'){
                if(Tmp==0){
                    Start.first=i;
                    Start.second=j;
                    Tmp++;
                }else{
                    End.first=i;
                    End.second=j;
                }
            }
            Visit[i][j][0] = Visit[i][j][1] = Visit[i][j][2] = Visit[i][j][3] = INF;
        }
    }
}

pair<int, int> Change_Direct(int Cur_Dir){
    pair<int, int> R; // 빛을 받은 거울은 2가지 방향으로 변환 가능
    if(Cur_Dir == 0 || Cur_Dir ==1){ //현재 좌 or 우로 빛 진행
        R.first =2;
        R.second =3;
    }
    else if (Cur_Dir ==2 || Cur_Dir ==3){ //현재 위 or 아래로 빛 진행
        R.first =0;
        R.second = 1;
    }
    return R;
}

void BFS(){
    while(Q.empty()==0)
    {
        int x=Q.front().x;
        int y=Q.front().y;
        int dir = Q.front().Dir;
        Q.pop();
        
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        pair<int, int> nd = Change_Direct(dir);
        
        if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
        if(MAP[nx][ny]=='*') continue;
        else if(MAP[nx][ny]=='!') //거울 설치
        {
            if(Visit[nx][ny][dir] > Visit[x][y][dir])
            {
                Visit[nx][ny][dir] = Visit[x][y][dir];
                Pos Temp;
                Temp.x=nx;
                Temp.y=ny;
                Temp.Dir = dir;
                Q.push(Temp); //새로 갱신
            }
            if(Visit[nx][ny][nd.first] > Visit[x][y][dir]+1){
                Visit[nx][ny][nd.first] = Visit[x][y][dir]+1;
                Pos Temp;
                Temp.x=nx;
                Temp.y=ny;
                Temp.Dir = nd.first;
                Q.push(Temp); //새로 갱신
            }
            if(Visit[nx][ny][nd.second] > Visit[x][y][dir]+1){
                Visit[nx][ny][nd.second] = Visit[x][y][dir]+1;
                Pos Temp;
                Temp.x=nx;
                Temp.y=ny;
                Temp.Dir = nd.second;
                Q.push(Temp);
            }
        }
        else if(MAP[nx][ny]=='.'){
            if(Visit[nx][ny][dir] > Visit[x][y][dir]){
                Visit[nx][ny][dir] = Visit[x][y][dir];
                Pos Temp;
                Temp.x=nx;
                Temp.y=ny;
                Temp.Dir = dir;
                Q.push(Temp);
            }
        }
        else if(MAP[nx][ny]=='#'){
            if(Visit[nx][ny][dir]>Visit[x][y][dir]){
                Visit[nx][ny][dir]=Visit[x][y][dir];
            }
        }
    }
}

void Solution(){
    for(int i=0; i<4; i++){
        Pos Temp;
        Temp.x=Start.first;
        Temp.y=Start.second;
        Temp.Dir = i;
        Q.push(Temp);
        Visit[Start.first][Start.second][i]=0;
    }
    BFS();
    int Answer = INF;
    for(int i=0; i<4; i++){
        if(Answer>Visit[End.first][End.second][i]){
            Answer = Visit[End.first][End.second][i];
        }
    }
    cout<<Answer<<'\n';
}


int main(){
    fastio;
    Input();
    Solution();
    return 0;
}

<참고>

https://yabmoons.tistory.com/195

<풀이>

골드3 어렵다...

거울을 설치할 시 빛이 바뀔 수 있는 모든 방향을 탐색해야 함

 

1. 좌표 & 방향을 관리하기 위한 구조체 Pos를 선언 

2. Start와 End에 출구와 입구 (#)를 구분해서 좌표를 pair로 저장

3. 빛의 첫 진행방향은 동서남북 모두를 탐색해야함

4. queue의 자료형을 struct형으로 넣고 초기 queue의 원소를 시작점 + 동서남북 넣기

5. 중복 탐색을 방지하기 위해 Visit[][][4]의 3차원 배열 사용 -> 같은 좌표에 있더라도 빛의 진행방향에 따라 결과가 달라짐

Visit[A][B][C]=D는 (A,B)에서 빛이 C방향으로 진행하고 있을 때, D개의 문이 설치됨 (작을 수록 더 적은 거울로 이동함)

6. 방향은 dx, dy로 오, 왼, 아래, 위 (엑셀 표로 생각)

7. Change_Direct는 빛이 좌/우로 진행할 때는 위아래, 빛이 위/아래로 진행할 때는 좌/우로 진행함(거울 반사) -> nx, ny, nd에 기록

8. if(Visit[nx][ny][nd.first] > Visit[x][y][dir]+1){

Visit[nx][ny][nd.first] = Visit[x][y][dir]+1;

Q.push({nx, ny, nd.first}); } 와 

if(Visit[nx][ny][nd.second] > Visit[x][y][dir]+1){

Visit[nx][ny][nd.second] = Visit[x][y][dir]+1;

Q.push({nx, ny, nd.second}); }를 진행해서 거울이 반사해서 위치한 곳에 대한 검사

9. 도착점에서 4가지 방향 중 Visit 값이 가장 작은 값을 최종적으로 찾음