[백준 6087] 레이저 통신 C++

6087번: 레이저 통신

BFS

---

1. 문제 해결 아이디어

 

처음에 시뮬레이션 문제인가? 생각했는데 그냥 BFS에 조건이 몇 개 추가된 문제였다.

 

먼저 DP풀듯이 각 칸에 도달하기 위한 최소 거울의 개수를 구해야 겠다는 생각을 했다.

그리고 이미 방문한 칸에 다시 도달할 수 있어야 올바른 최솟값을 구할 수 있다고 깨달았다.

가장 기본적으로, 주어진 W, H 범위 내에서만 움직여야하고, 벽인 경우 que에 넣으면 안된다.

que의 초기값이 하나의 점이 아니라 임의의 C에서 4방향으로 가는 칸을 push해준다.

 

queue에 있는 좌표들에게 지금까지 사용한 거울의 개수와 직전에 움직였던 방향 정보를 추가로 가지게 했다.

 

bfs 함수를 만들면서 어색했던 점은 visited배열을 사용하는 부분이 없는 대신

다음에 이동할 좌표의 거울 개수가 더 작다면 continue하는 방식으로 약간의 중복이 발생하겠지만 모든 정보를 찾는 방법을 사용했다는 점이다.

---

2.  코드

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct P{
    int r, c;
    int dir;    // 0 1 2 3 : 동 서 남 북
    int mnum;
};
 
const int INF = 1e9+7;
int W, H;
int Map[101][101];
int mirrornum[101][101];
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
vector<pair<int, int> > Cs;
 
void input(){
    string str;
    cin >> W >> H;
    for(int i = 0; i < H; i++){
        cin >> str;
        for(int j = 0; j < W; j++){
            char cc = str[j];
            switch (cc){
            case '.': Map[i][j] = 1; break;
            case 'C':
                Map[i][j] = 2; 
                Cs.push_back({i, j});
                break;
            case '*': Map[i][j] = 0; break;
            default: break;
            }
            mirrornum[i][j] = INF;
        }
    }
}
 
void bfs(){
    queue<P> que;
    for(int k = 0; k < 4; k++){
        que.push({Cs[0].first, Cs[0].second, k, 0});
    }
    
    while(!que.empty()){
        P now = que.front();
        que.pop();
        
        if(now.r == Cs[1].first && now.c == Cs[1].second) continue;
        
        for(int k = 0; k < 4; k++){
            int nr = now.r + dr[k];
            int nc = now.c + dc[k];
            
            if(nr < 0 || nr >= H || nc < 0 || nc >= W || !Map[nr][nc]) continue;
            
            if(now.dir != k){
                if(mirrornum[nr][nc] < now.mnum + 1) continue;
                mirrornum[nr][nc] = now.mnum + 1;
                que.push({nr, nc, k, now.mnum + 1});
            }
            else{
                if(mirrornum[nr][nc] < now.mnum) continue;
                mirrornum[nr][nc] = now.mnum;
                que.push({nr, nc, k, now.mnum});
            }
        }
    }
}
 
int main(){
    input();
    bfs();
    cout << mirrornum[Cs[1].first][Cs[1].second];
    return 0;
}