[Dijkstra] 6087번 레이저 통신

6087번 레이저 통신

 

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

 

문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

 

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

 

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

예제 입력

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

 

예제 출력

3

 

해결방법

다익스트라 탐색을 통해 최소의 방법으로 이동하는 문제이다

이 문제는 사실 거울설치 문제와 거의 동일하다

그래서 어렵지 않게 솔루션을 찾았을 수 있었다

 

⭐️ 솔루션 ⭐️

• N ≤ 100
• 우선순위 큐의 시간 복잡도 : E lov V

 

1. 2개의 'C' 를 연결해야함
2. 빈칸에는 \ / 거울을 설치 할 수 있고, 설치를 안할 수도 있다
3. 최소 거울 개수는 ??

 

보통 최단거리가 아닌(또는 포함) 다른 조건을 최소화 하는 문제는 다익스트라 알고리즘 이나 우선순위 큐로 접근 가능하다!!!

 

처음에는 dist[MAX][MAX] 를 선언하여 코드를 작성하였다

하지만 한 노드는 '\' 거울을 설치하는 경우 , '/' 거울을 설치하는 경우 , 설치하지 않는 경우 로 여러 상태가 존재할 수 있다

 

\ 거울을 설치하는 경우 는 현재 방향에서 -90도 회전을 할 것이다

/ 거울을 설치하는 경우 는 현재 방향에서 90도 회전을 할 것이다

설치하지 않는 경우 는 현재 방향을 그래도 유지할 것이다

 

따라서 dist 배열을 dist[MAX][MAX][4] 로 수정하여 다익스트라 탐색을 이어나갔다

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 101
#define INF 987654321
using namespace std;

struct node {
    int x,y,dir,cnt;
    
    node() { }
    node(int _x,int _y,int _dir,int _cnt) : x(_x),y(_y),dir(_dir),cnt(_cnt) { }
    
    bool operator > (const node &n) const{
        return cnt > n.cnt;
    }
};

int n,m;

char map[MAX][MAX];
int dist[MAX][MAX][4];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

vector<node> c;

int changeDir(int dir,int i){
    if(i==1){
        if(dir==0 || dir==1) return 2;
        else if(dir==2 || dir==3) return 0;
    }else{
        if(dir==0 || dir==1) return 3;
        else if(dir==2 || dir==3) return 1;
    }
    return 0;
}

void dijkstra(){
    priority_queue<node,vector<node>,greater<node>> pq;
    
    int x = c[0].x;
    int y = c[0].y;
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
        if(map[nx][ny] == '*') continue;
        
        pq.push(node(x,y,i,0));
        dist[x][y][i] = 0;
    }
    
    while(!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int dir = pq.top().dir;
        int cnt = pq.top().cnt;
        pq.pop();
        
        if(x==c[1].x && y==c[1].y){
            cout << cnt << "\n";
            return;
        }
        
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
        if(map[nx][ny] == '*') continue;
        
        
        // 거울을 설치하는 경우
        if(map[nx][ny] == '.'){
            for(int j=1; j<=2; j++){
                int nd = changeDir(dir,j);
                
                if(dist[nx][ny][nd] > dist[x][y][dir] + 1){
                    dist[nx][ny][nd] = dist[x][y][dir] + 1;
                    pq.push(node(nx,ny,nd,cnt+1));
                }
            }
        }
        
        // 설치하지 않고 가는 경우
        if(dist[nx][ny][dir] > dist[x][y][dir]){
            dist[nx][ny][dir] = dist[x][y][dir];
            pq.push(node(nx,ny,dir,cnt));
        }
        
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> m >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
            
            if(map[i][j] == 'C') c.push_back(node(i,j,0,0));
            
            for(int k=0; k<4; k++){
                dist[i][j][k] = INF;
            }
        }
    }
    
    dijkstra();
    
    return 0;
}