BOJ 2151 거울 설치

백준 BOJ 2151 C++

거울 설치

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

 

 

1) BFS 문제 -- BFS는 이제 빠른 시간 내에 풀 줄 안다고 생각했는데 .. 오래 걸렸다! 더 열심히!

2) 코드를 깔끔하게 짠다고(중복 줄이기, 불필요한 연산 줄이기) 생각을 오래 했는데.. 부족한 것 같다.

3) 거울이 없을 때는 공통 부분이므로 따로 조건문 안에 넣지 않았고, 다음 칸이 '!'일 때 방향 전환해서 큐에 넣었다.

 

/**
 * 200610
 * 2151 거울 설치
 * BFS
 * */

#include <iostream>
#include <queue>
#define INF 987654321
using namespace std;

int N;
char map[52][52];
int check[52][52][4];
int sx=-1, sy=-1, ex, ey;

int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int ans = 987654321;

struct info{
    int x, y, dir, cnt;
};

void bfs(){
    queue <info> q;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=0; k<4; k++)
                check[i][j][k] = INF;

    for(int k=0; k<4; k++){
        q.push();
        check[sx][sy][k] = 0;
    }

    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        int cnt = q.front().cnt;
        q.pop();

        if(x==ex && y==ey) {
            if(ans > cnt) ans = cnt;
        }

        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(0<=nx && nx<N && 0<=ny && ny<N){
            if(map[nx][ny]=='*') continue;

             // 거울 X
            if(check[nx][ny][dir] > cnt){
                q.push();
                check[nx][ny][dir] = cnt;
            }

            if(map[nx][ny]=='!'){
                // 거울 O -- case1
                int nd = (dir+1)%4;
                if(check[nx][ny][nd] > cnt+1){
                    q.push();
                    check[nx][ny][nd] = cnt+1;
                }

                // 거울 O -- case2
                nd = (dir+3)%4;
                if(check[nx][ny][nd] > cnt+1){
                    q.push();
                    check[nx][ny][nd] = cnt+1;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++){
        string s;
        cin >> s;
        for(int j=0; j<N; j++){
            map[i][j] = s[j];
            if(map[i][j]=='#'){
                map[i][j]='.';
                if(sx==-1 && sy==-1){
                    sx = i;
                    sy = j;
                }
                else {
                    ex = i;
                    ey = j;
                }
            }
        }
    }

    bfs();
    cout << ans << '\n';
    
    return 0;
}