[ 백준 ] 6087번 - 레이저 통신 (C++)

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

6087번: 레이저 통신

 

 

[ 문제풀이 ]

 

1. 맵을 입력받고, 문의 위치를 vector에 저장합니다.

 

2. visited [ y ][ x ][ dir ] 배열을 만들어 방문 여부를 저장합니다.

 

3. pos struct를 만들어 y좌표, x좌표, 빛의 방향, 거울의 개수를 저장합니다.

 

4. dijkstra를 이용하여 거울의 개수가 적은 순으로 priority_queue에서 뽑고, '.'을 만나면 pq에 넣습니다.

 

5. vector에 저장된 문의 좌표와 현재 좌표가 일치하면 cnt의 값을 출력해줍니다.

 

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int W, H;
char arr[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[101][101][4];
vector<pair<int, int>> laser;
 
struct pos {
    int y;
    int x;
    int cnt;
    int dir;
};
 
struct cmp {
    bool operator()(pos right, pos left) {
        return left.cnt < right.cnt;
    }
};
 
int main()
{
    scanf("%d %d", &W, &H);
 
    for (int i = 0; i < H; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (arr[i][j] == 'C') {
                laser.emplace_back(i, j);
            }
        }
    }
 
    priority_queue<pos, vector<pos>, cmp> pq;
    for (int i = 0; i < 4; i++) {
        pq.push({ laser[0].first, laser[0].second, 0, i });
    }
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int cnt = pq.top().cnt;
        const int dir = pq.top().dir;
        pq.pop();
 
        if (visited[y][x][dir] == 1) continue;
        visited[y][x][dir] = 1;
 
        if (y == laser[1].first && x == laser[1].second) {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < H && xx >= 0 && xx < W) {
                if (arr[yy][xx] == '*') continue;
                if (visited[yy][xx][dir] != 1) {
                    if (i != dir) {
                        pq.push({ yy,xx,cnt + 1,i });
                    }
                    else {
                        pq.push({ yy,xx,cnt,i });
                    }
                }
            }
        }
    }
}