BOJ
BOJ::6087 레이저 통신
BOJ Gold 4
BOJ::6087 레이저 통신
- Link : BOJ::6087
- Level : Gold 4
- tag :
시사점
이해(4)
- 시작점 C에서 도착점 C로 갈 수 있도록 최소한의 거울을 설치하는 문제입니다.
- 중요한 것은, 벽과 ‘C’가 아닌 모든 정점에 거울을 설치할 수 있다는 점입니다.
설계, 손 코딩(4)
- 손으로 중심이 되는 코드를 구현합니다.
- 상태의 정의는 다음과 같습니다.
- bool status[ x ][ y ][ 4방향 ][ maxn * maxn ]
- 하지만, 사이즈가 커서 메모리 초과의 우려가 있습니다.
- 따라서 아래와 같이 변경하여 풀이하였습니다.
- int status[ x ][ y ][ 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)
- n과 m을 바꿔서 받는 실수를 하였습니다.