[BOJ] 레이저 통신 - Compy's Blog

레이저 통신

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(1 ≤ W, H ≤ 100)	BFS(너비우선탐색)

이거는 어제 풀었던 문제랑 그냥 똑같다고 생각하면 되는데요.. 그래서 짜둔 코드를 안 지워서 그대로 필요한 것들만 빼고 지운 다음에 제출하니까 틀렸습니다… 그래서 음 뭐지? 하고 반례를 다 넣어봤는데 다 정답.. 시간 초과도 아님.. 애초에 무조건 돌아가는 코드라 생각도 안 했는데.. 이게 무슨?

그래서 조금 다시 체계적으로 작성하려고 시간을 좀 씀.. 그랬더니? 정답.. 뭐지? 도대체 왜 이러는거냐 백준

아우.. 이런 것때문에 시간이 소모된게 너무 아까움.. 다들 조심하시고 만약 막히면 그냥 다 지우고 다시 짜세요 그게 답입니다.

하튼 즐거운 ps 되시길

정답 코드

#include <iostream>
#include <queue>
using namespace std;

struct pos {
    int dir;
    int y, x;
    int cost;
};

int dx[] = {0,1,-1,0,0}, dy[] = {0,0,0,1,-1};
int W, H;
char board[101][101];
int cost[101][101][4];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> W >> H;
    pos start = {-1,-1,-1,0}, end;
    bool check = true;
    
    for(int i=0; i<H; i++) for(int j=0; j<W; j++) {
        cin >> board[i][j];
        if(board[i][j] == 'C') {
            if(check) { start = {0,i,j,0}; check = false; }
            else end = {0,i,j,0};
            board[i][j] = '.';
        }
        for(int d=0;d<4;d++) cost[i][j][d] = 1e9;
    }
    
    queue<pos> q;
    q.push({1, start.y, start.x, 0});
    q.push({2, start.y, start.x, 0});
    q.push({3, start.y, start.x, 0});
    q.push({4, start.y, start.x, 0});
    
    
    while(!q.empty()){
        pos cur = q.front(); q.pop();
        
        int y = cur.y, x = cur.x, dir = cur.dir, c = cur.cost;
        
//        cout <<"check!: "<< c << " " << cost[y][x][dir-1] << "\n";
        if(c > cost[y][x][dir-1]) continue;
        
        if(y == end.y && x == end.x) continue;
        
        for(int nd=1; nd<=4; nd++){
            int ny = y + dy[nd];
            int nx = x + dx[nd];
            
            if(ny<0 || nx<0 || ny>=H || nx>=W) continue;
            if(board[ny][nx] == '*') continue;
            
            // 1:동, 2:서, 3:남, 4:북
            if(dir != nd && ((dir<=2 && nd<=2) || (dir>=3 && nd>=3))) continue;
            
            int newCost = c + (dir != nd);
            
            if(cost[ny][nx][nd-1] > newCost){
                cost[ny][nx][nd-1] = newCost;
                q.push({nd, ny, nx, newCost});
            }
        }
    }
    
//    for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){
//        if(cost[i][j][0] == 1e9) cout << "o ";
//        else cout << cost[i][j][0] << " ";
//    }
//        cout << "\n";
//    }

    
    
    int ans = 1e9;
    for(int d=0; d<4; d++)
        ans = min(ans, cost[end.y][end.x][d]);
    
    cout << ans;
    return 0;
}