문제

6087번: 레이저 통신

풀이

bfs를 십자 직선 방향으로 모든 노드와 이어져 있다 생각하고 탐색했다.
벽을 만난다거나, 인덱스의 범위를 넘어가는 경우까지 while을 이용해서 모두 탐색했다.

이때 이미 탐색한 부분의 중복처리를 어떻게 해야할지 고민이 되었는데,
간단하게 이미 탐색한 부분의 값이 현재값+1 보다 작거나 같은 경우를 제외하고는 모두 탐색한다.

직선 방향으로 모두 탐색하기 때문에 그림을 그려서 생각해보면 금방 알 수 있었다.

모두 탐색을 완료한 뒤 C 의 위치중 시작하지 않은 곳의 값을 가져와서 -1한다.
시작 지점을 0으로 하고 십자 방향으로 탐색할 때 +1 된 값을 저장하였기 때문에 직선의 수를 센 것이다. 따라서 거울의 개수는 그 값의 -1이다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Pos{
    int x;
    int y;

    bool operator==(Pos input){
        return input.x == x && input.y == y;
    }
    Pos operator+(Pos input){
        Pos res;
        res.x = input.x + this->x;
        res.y = input.y + this->y;
        return res;
    }
};

vector<Pos> dir { {0,1}, {1,0}, {-1, 0}, {0, -1} };

int w, h;
vector<vector<int>> dist;
vector<vector<bool>> isWall;

bool OOB(Pos input){
    return input.x < 0 || input.x >= h || input.y < 0 || input.y >= w;
}

void bfs(Pos start){
    queue<Pos> q;
    q.push(start);
    dist[start.x][start.y] = 0;

    while (!q.empty()){
        Pos cur = q.front();
        q.pop();
        for (Pos d: dir){
            Pos next = cur + d;
            while( !( OOB(next) || isWall[next.x][next.y] ) ){
                // if (OOB(next)) break;
                // if (isWall[next.x][next.y]) break;
                if (dist[next.x][next.y] > dist[cur.x][cur.y]+1){
                    dist[next.x][next.y] = dist[cur.x][cur.y]+1;
                    q.push(next);
                }
                next = next + d;
            }
        }
    }
}

int main () {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> w >> h;
    vector<Pos> CPos;
    dist = vector<vector<int>> (h, vector<int>(w, w*h+1));
    isWall = vector<vector<bool>> (h, vector<bool>(w, false));
    for (int i=0; i<h; i++){
        string input;
        cin >> input;
        for (int j=0; j<w; j++){
            if (input[j] == '*') isWall[i][j] = true;
            if (input[j] == 'C') {
                CPos.push_back( {i,j} );
            }
        }
    }
    dist[CPos[0].x][CPos[0].y] = 0;
    bfs(CPos[0]);
    cout << dist[CPos[1].x][CPos[1].y]-1 << endl;
}