[백준] 6087 레이저 통신

90도로 방향을 바꾸기 위해서는 거울이 1개 필요하다

이 때 C -> C까지 갈 때 최소 거울을 찾는 문제다

 

다익스트라를 이용해서 d[100][100][4]로 각 방향으로 갈 때 최소비용을 구했다

만약 90도 방향이 바뀐다면 그때만 비용을 +1 해줬다

 

마지막 도착지에서는 4방향 중 가격이 가장 싼 곳을 출력하면 된다

 

다른 사람들 풀이를보니 그냥 bfs만 돌려도 충분히 풀 수 있다

내가 방향이 바뀌면 새로운 점들을 queue에 비용을 증가시켜 넣고

현재 정점에서는 다시 한칸 앞으로가서 비용없이 또 탐색을 하면 된다

 

소스코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m,ans=1e9,sx=-1,sy,ex,ey;
int d[111][111][4];
char map[111][111];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
bool inner(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < m);
}
int main() {
    //freopen("input.txt", "r", stdin);
    scanf(" %d %d", &m, &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %1c", &map[i][j]);
            if (map[i][j] == 'C') {
                if (sx == -1) sx = i, sy = j;
                else ex = i, ey = j;
            }
        }
    }
    
    memset(d, -1, sizeof(d));
    priority_queue<pair<pair<int, int>, pair<int, int>>> pq;
    for(int i=0;i<4;i++) pq.push({ {0,i},{sx,sy} });
    
    while (!pq.empty()) {
        int cost = -pq.top().first.first;
        int op = pq.top().first.second;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
        if (d[x][y][op] != -1) continue;
        d[x][y][op] = cost;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int ncost = -cost;
            if (op != -1 && ((op + 1) % 4 == i || (op + 3) % 4 == i)) ncost -= 1;
            if (!inner(nx, ny)) continue;
            if (map[nx][ny] == '*') continue;
            if (d[nx][ny][i] != -1) continue;
            pq.push({ {ncost,i},{nx,ny} });
        }
    }
    for (int i = 0; i < 4; i++) {
        if (d[ex][ey][i] == -1) continue;
        ans = min(ans, d[ex][ey][i]);
    }
    printf("%d\n", ans);
}