[Dijkstra] 2151번 거울 설치

2151번 거울 설치

 

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

 

문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

 

입력

첫째 줄에 집의 크기 N (1 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.

 

출력

첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

 

예제 입력

5
***#*
*.!.*
*!.!*
*.!.*
*#***

8
***#****
*!.!..!*
*......*
*..*...*
*!!....*
*.!!..!*
*......*
***#****

5
***#!
*.*..
*!.*.
*!..!
*#***

8
****!.#!
*...!..!
*.......
#......!
*......*
*......*
*......*
********

3
...
*!#
#!!

 

예제 출력

2

4

3

2

1

 

해결방법

참고블로그1 : https://lyzqm.blogspot.com/2017/04/2151.html

참고블로그2 : http://wondy1128.tistory.com/171

 

4시간이 걸린 문제이다... 흑흑

BFS 탐색으로 문제를 풀다가 블로그를 참고하여 결국 다익스트라로 문제를 해결했다

 

⭐️ 1차 시도 ⭐️

틀렸습니다

 

단순하게 BFS 탐색으로 접근했다

첫 번째 문의 방향을 구한다음 큐에 넣고 최단거리 탐색을 수행했다

하지만 문제는 최단거리가 아닌 최소한의 방법을 사용하는 탐색이었다

최소 방법 탐색은 우선순위 큐 , 다익스트라 알고리즘 을 사용하여 해결해야 했다

 

 

⭐️ 2차 시도 ⭐️

틀렸습니다

 

우선순위 큐를 사용하여 문제를 접근했다

질문 검색을 하다가 간과했던 사실이 있었다

1. 문의 방향은 하나가 아닌 여러개일 수 있다
2. 최소의 거울을 설치하여 이동해야 한다
3. 거울을 설치하여 방향을 바꿀수도, 설치하지 않고 그대로 진행할 수도 있다

 

따라서 처음 문의 방향을 큐에 넣을 때, 맵을 벗어나지 않고 벽이 아닌 모든 방향을 넣어줬다

// 방향 세팅
void setDoorDirection(){
    int x = door[0].x;
    int y = door[0].y;
    for(int d=0; d<4; d++){
        int nx = x + dx[d];
        int ny = y + dy[d];
        
        if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
        if(map[nx][ny] == '*') continue;
        
        pq.push(node(x,y,d,0));
        visited[x][y][d] = true;
    }
}

 

또한 다음 노드의 상태에 따라 진행여부를 달리해줬다

먼저 거울인 경우, 방향에 따라 회전을 시켜서 탐색을 진행했다

if(map[nx][ny] == '!'){
    if(d==0 || d==1){
        for(int i=2; i<=3; i++){
            pq.push(node(nx,ny,i,cnt+1));
            visited[nx][ny][i] = true;
        }
    }
    if(d==2 || d==3){
        for(int i=0; i<=1; i++){
            pq.push(node(nx,ny,i,cnt+1));
            visited[nx][ny][i] = true;
        }
    }
}

 

그리고 나머지 경우 (빈 칸, 문, 거울 설치X) 에 대해서 탐색을 진행해줬다

// 나머지 경우
pq.push(node(nx,ny,d,cnt));
visited[nx][ny][d] = true;

 

하지만 어떤 예외가 있는지 결과가 나오지 않았다 😭😭

 

 

⭐️ 3차 시도 ⭐️

맞았습니다

 

테스트케이스를 발견했다!!

// INPUT
3
...
*!#
#!!

// OUTPUT
>> 1

 

이 TC 에서는 답이 2로 나왔다

디버깅을 해보니 문(1,2) 에서 왼쪽(1,1) 아래쪽(2,2) 으로 거울을 설치한 다음의 경우에서 문제가 발생했다

(1,1) 에서 (2,1) 로 이동 후, visited 을 true 로 설정하게 되면 (2,2) 에서는 거울을 설치하고 갈 수 있지만 이미 방문했기 때문에 더이상 진행되지 못한다

나는 우선순위 큐만 사용하면 된다고 생각했는데 다익스트라 알고리즘의 Relax연산을 같이 수행해야했다

 

bool형의 visited 배열이 아닌 int형의 dist 배열로 변경한 후, Relax 연산을 적용하니 결과가 잘나왔다!

 

다음 노드가 거울인 경우

if(map[nx][ny] == '!'){
    if(d==0 || d==1){
        for(int i=2; i<=3; i++){
            if(dist[nx][ny][i] > dist[x][y][d] + 1){
                pq.push(node(nx,ny,i,cnt+1));
                dist[nx][ny][i] = dist[x][y][d] + 1;
            }
        }
    }
    
    if(d==2 || d==3){
        for(int i=0; i<=1; i++){
            if(dist[nx][ny][i] > dist[x][y][d] + 1){
                pq.push(node(nx,ny,i,cnt+1));
                dist[nx][ny][i] = dist[x][y][d] + 1;
            }
        }
    }
}

 

나머지 경우 (빈 칸, 문, 거울 설치X)

// 나머지 경우
if(dist[nx][ny][d] > dist[x][y][d]){
    pq.push(node(nx,ny,d,cnt));
    dist[nx][ny][d] = dist[x][y][d];
}

 

 

 

소스코드

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

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

int n;

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

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

priority_queue<node, vector<node>, greater<node>> pq;
vector<node> door;

// 방향 세팅
void setDoorDirection(){
    int x = door[0].x;
    int y = door[0].y;
    for(int d=0; d<4; d++){
        int nx = x + dx[d];
        int ny = y + dy[d];
        
        if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
        if(map[nx][ny] == '*') continue;
        
        pq.push(node(x,y,d,0));
        dist[x][y][d] = 0;
    }
}

void dijkstra(){
    while(!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int d = pq.top().d;
        int cnt = pq.top().cnt;
        pq.pop();
        
        if(x==door[1].x && y==door[1].y){
            cout << cnt << "\n";
            return;
        }
        
        int nx = x + dx[d];
        int ny = y + dy[d];
        
        if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
        if(map[nx][ny] == '*') continue;
        
        if(map[nx][ny] == '!'){
            if(d==0 || d==1){
                for(int i=2; i<=3; i++){
                    if(dist[nx][ny][i] > dist[x][y][d] + 1){
                        pq.push(node(nx,ny,i,cnt+1));
                        dist[nx][ny][i] = dist[x][y][d] + 1;
                    }
                }
            }
            
            if(d==2 || d==3){
                for(int i=0; i<=1; i++){
                    if(dist[nx][ny][i] > dist[x][y][d] + 1){
                        pq.push(node(nx,ny,i,cnt+1));
                        dist[nx][ny][i] = dist[x][y][d] + 1;
                    }
                }
            }
        }
        
        // 나머지 경우
        if(dist[nx][ny][d] > dist[x][y][d]){
            pq.push(node(nx,ny,d,cnt));
            dist[nx][ny][d] = dist[x][y][d];
        }
    }
}

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