백준 6087 - C++, BFS

6087번: 레이저 통신

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int w, h;
pair<int, int> startP, endP;
bool getStartPoint;
char map[101][101];
int count[101][101];

int goX[4] = { 0, 0, 1, -1 };
int goY[4] = { 1, -1, 0, 0 };
// 0 = 위, 1 = 아래, 2 = 오른쪽, 3 = 왼쪽



void MirrorSearch(){
    queue<pair<pair<int, int>, pair<int, int>>> q; // x, y, mirrorcount, direction
    count[startP.first][startP.second] = 0;
    // Start
    for(int i = 0; i < 4; i++)
        q.push(make_pair(make_pair(startP.first, startP.second), make_pair(0, i)));

    while(!q.empty()){
        int curX = q.front().first.first;
        int curY = q.front().first.second;
        int mirrorCount = q.front().second.first;
        int curDir = q.front().second.second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nextX = curX + goX[i];
            int nextY = curY + goY[i];
            int nextCount = mirrorCount;

            if(nextX < 0 || nextX >= h || nextY < 0 || nextY >= w)
                continue;
            
            if(map[nextX][nextY] == '*')
                continue;
            
            if(i != curDir)
                nextCount = mirrorCount + 1;

            if(count[nextX][nextY] == -1 || count[nextX][nextY] >= nextCount){
                q.push(make_pair(make_pair(nextX, nextY), make_pair(nextCount, i)));
                count[nextX][nextY] = nextCount;
            }
        }
    }
    
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // input
    cin >> w >> h;

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> map[i][j];

            if(map[i][j] == 'C'){
                if(!getStartPoint){
                    getStartPoint = true;
                    startP.first = i;
                    startP.second = j;
                }
                else{
                    endP.first = i;
                    endP.second = j;
                } 
            }
        }
    }

    // solution
    memset(count, -1, sizeof(count));
    MirrorSearch();

    // print
    cout << count[endP.first][endP.second] << '\n';
}

---

기본적인 BFS 이지만 단순 거리가 아닌 거울의 갯수를 구하는 문제입니다. 큐에 추가적으로 2가지 정보를 더 넣어줘야 하는데

 

- 현재 지점까지 오는데 사용한 거울의 갯수

- 지금의 방향 (이전 좌표에서 어떻게 이동을 했는지 0~3의 수로 저장)

 

 이렇게 2가지 정보를 큐가 계속 들고 있으면서 다음 지점에 사용하면 됩니다. 방향의 경우 위 goX, goY의 조합으로 사용되는 순서를 이용해 0~3까지 주면 됩니다.

 

 마지막으로 시작 지점을 넣을때 한 방향만 넣고 했다 틀렸는데 처음 시작 전 큐에 시작 지점을 기준으로 4개 방향을 넣어줘야 합니다.