Baekjoon 6087번 레이저 통신

문제

https://www.acmicpc.net/problem/6087

걸린 시간

01 : 04 : 33 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int w, h;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<pair<int, int>> C;
vector<vector<char>> Map;
vector<vector<vector<int>>> visited;

struct light{
    int y;
    int x;
    int d; // direction
    int m; // mirror
    light(int y, int x, int d, int m){
        this->y = y;
        this->x = x;
        this->d = d;
        this->m = m;
    }
};

int bfs(){
    int sy = C[0].first;
    int sx = C[0].second;
    int ey = C[1].first;
    int ex = C[1].second;
    visited.resize(4, vector<vector<int>>(h, vector<int>(w, 0)));    
    queue<light> q;
    for(int i = 0; i < 4; i++){
        int ny = sy+dy[i];
        int nx = sx+dx[i];
        if(0 <= ny && ny < h && 0 <= nx && nx < w){
            if(Map[ny][nx] != '*'){
                visited[i][sy][sx] = 1;
                q.push(light(sy, sx, i, 0));
            }
        }
    }
    while(!q.empty()){
        int y = q.front().y;
        int x = q.front().x;
        int d = q.front().d;
        int m = q.front().m;
        q.pop();
        int ny = y, nx = x;
        while(true){
            ny += dy[d];
            nx += dx[d];
            if(0 > ny || h <= ny || 0 > nx || w <= nx || Map[ny][nx] == '*') break;
            if(ny == ey && nx == ex) return m;
            for(int i = 0; i < 4; i++){
                if(i != d && !visited[i][ny][nx]){
                    visited[i][ny][nx] = 1;
                    q.push(light(ny, nx, i, m+1));
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> w >> h;
    Map.resize(h, vector<char>(w));
    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            cin >> Map[y][x];
            if(Map[y][x] == 'C')
                C.push_back(make_pair(y, x));
        }
    }
    cout << bfs();
    return 0;
}

레이저가 진행할 수 있는 방향에 거울을 모두 놓아보는 방법이다. 현재 진행하고 있는 빛이 벽 혹은 목적지에 도달하기 전 거울을 설치해 방향이 바뀐 빛의 경로를 탐색해서는 안된다.