BOJ::6087 레이저 통신

시사점

이해(4)

설계, 손 코딩(4)

시간 복잡도

공간 복잡도

손 코딩 후 문제 리뷰(x)

구현(6)

함수 List

업데이트 되는 변수

실제 구현

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXN = 100;
struct cell{int x; int y; int d; int used;
    bool operator<(const struct cell& t) const{
        return used > t.used;
    }
};
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
const int dir[4][2]={ {1, 3}, {0, 2}, {1, 3}, {0, 2} };
using namespace std;
const int INF = numeric_limits<int>::max();

int n, m, sx = -1, sy, ex, ey;
char a[MAXN][MAXN];
int status[MAXN][MAXN][4];
priority_queue<cell> pq;
void input(){
    cin >> m >> n; // 실수(3) :: n, m바꿔서 받음
    rep(i, 0, n){
        rep(j, 0, m){
            cin >> a[i][j];
            if(a[i][j] == 'C'){
                if(sx == -1) sx = i, sy = j;
                else ex = i, ey = j;
                a[i][j] = '.';
            }
            rep(k, 0, 4) status[i][j][k] = INF;
        }
    }
}
bool over(int x, int y){return (x<0 || y<0 || x>=n || y>=m);}
void bfs(){
    rep(i, 0, 4){
        pq.push({sx, sy, i, 0});
        status[sx][sy][i] = 0;
    }
    while(!pq.empty()){
        int x = pq.top().x, y = pq.top().y, d = pq.top().d, used = pq.top().used; pq.pop();
        if(x == ex &&  y == ey){
            cout << used << endl;
            return;
        }
        int nx = x+dx[d], ny = y+dy[d];
        while(!over(nx, ny) && a[nx][ny] == '.'){
            rep(i, 0, 2){
                int nd = dir[d][i];
                if(status[nx][ny][nd] > used+1){
                    status[nx][ny][nd] = used+1;
                    pq.push({nx, ny, nd, used+1});
                }
            }
            if(status[nx][ny][d] > used){
                status[nx][ny][d] = used;
                pq.push({nx, ny, d, used});
            }
            nx += dx[d], ny += dy[d];
        }
    }
}
void process(){
    input();
    bfs();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

구현 후 코드리뷰 + 예제 돌려보기(x)

디버깅(3)

좋은 코드

최적화