백준 2151

문제

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

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

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

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

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

 

 

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

풀이

다익스트라로 풀었다.

다음과 같은 예제가 있을때 첫번째 문부터 시작하면

다음과 같은 방향으로 갈 수 있고, 거울을 지나지 않았기 때문에 사용한 거울의 개수를 0으로 체크한다.

다음 진행방향은 현재 지점이 거울이 아니었기 때문에 방향을 바꿀 수 없고, 그대로 진행해서 해당 거울로 가게된다.

그 다음 진행방향은 이렇게 되며,  현재 지점이 거울이기 때문에 사용한 거울 + 1을 하여 다음 지점으로 이동한다.

 

이러한 방식으로 [지점][방향]에 대한 최소 거울의 사용개수를 체크한다면 문제를 풀 수 있다.

 

현재 지점의 경우의 수는 3가지로, {#, ., !} 의 경우의 수가 있다.

#인 경우에는 방향의 제한이 없고

.인 경우에는 이전에 진행했던 방향대로 진행해야하며

!인 경우에는 이전에 진행했던 방향의 반대방향을 제외하고 이동할 수 있다고 가정했다.

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int N, dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0}, ans[51][51][4], ansNum = 987654322, startX, startY;
string board[51];
void solve(int x, int y) {
    queue<pair< pair<int, int>, pair<int, int> > >q;
    q.push(make_pair(make_pair(x, y), make_pair(-1, 0)));
    while(!q.empty()) {
        auto cur = q.front().first; int curDir = q.front().second.first; int curDist = q.front().second.second; q.pop();
        char curBoard = board[cur.first][cur.second];
        if(curBoard == '#') {
            for(int dir=0; dir<4; dir++) {
                int nx = cur.first + dx[dir];
                int ny = cur.second + dy[dir];
                if(nx<0||nx>=N||ny<0||ny>=N||board[nx][ny] == '*') continue;
                if(ans[nx][ny][dir] > curDist) {
                    ans[nx][ny][dir] = curDist;
                    q.push(make_pair(make_pair(nx,ny), make_pair(dir, curDist)));
                }
                if(board[nx][ny] == '#'&& (nx != startX || ny != startY)) ansNum = min(ansNum, ans[nx][ny][dir]);
            }
        }else if(curBoard == '!') {
            for(int dir=0; dir<4; dir++) {
                if(dir == (curDir+2)%4) continue;
                int nx = cur.first + dx[dir];
                int ny = cur.second + dy[dir];
                if(nx<0||nx>=N||ny<0||ny>=N||board[nx][ny] == '*') continue;
                int addiDist = (curDir == dir)?0:1;
                if(ans[nx][ny][dir] > curDist + addiDist) {
                    ans[nx][ny][dir] = curDist + addiDist;
                    q.push(make_pair(make_pair(nx,ny), make_pair(dir, curDist + addiDist)));
                }
                if(board[nx][ny] == '#' && (nx != startX || ny != startY)) ansNum = min(ansNum, ans[nx][ny][dir]);
            }
        }else if(curBoard == '.') {
            int nx = cur.first + dx[curDir];
            int ny = cur.second + dy[curDir];
            if(nx<0||nx>=N||ny<0||ny>=N||board[nx][ny] == '*') continue;
            if(ans[nx][ny][curDir] > curDist) {
                ans[nx][ny][curDir] = curDist;
                q.push(make_pair(make_pair(nx,ny), make_pair(curDir, curDist)));
            }
            if(board[nx][ny] == '#'&& (nx != startX || ny != startY)) ansNum = min(ansNum, ans[nx][ny][curDir]);
        }
    }
}
int main(){
    cin>>N;
    for(int i=0; i<N; i++) cin>>board[i];
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++){
            if(board[i][j] == '#'){
                startX = i; startY = j;
            }
            for(int k=0; k<4; k++)
                ans[i][j][k] = 987654321;
        }
    for(int i=0; i<4; i++)
        ans[startX][startY][i] = 0;
    solve(startX, startY);
    cout<<ansNum;
    

}