[ 백준 2151 ] 거울 설치 (C++)

백준의 거울설치(2151) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 처음에 문제를 읽을 때, 문제 이해가 안되서 굉장히 애를 많이 먹었다. 거울을 뭐 어떻게 설치해야 되는지도 모르겠고, 빛이 어떻

   게 반사되는지도 잘 이해가 되지 않았다. 다른 사람들의 코드와 설명을 참고하다보니, 전체적으로 이해를 할 수 있었다.

   문제를 이해한 사람이라면 지금부터 1) 까지의 내용은 읽지 않아도 된다 !

   먼저, 문제 이해부터 제대로 해보자. 거울을 45도로 기울어진 대각선 방향으로 설치해야하고, 거울은 양면거울이라고 했다.

   즉, 거울을 하나 설치하게 되면, 빛은 수직방향으로 꺽이게 된다. 하지만, 어느 수직방향인지는 우리가 선택해줘야 한다.

   예를 들어서 빛이 서쪽에서 동쪽으로 향하고 있다고 생각해보자. 이 때, 거울을 하나 만나게 되면, 이 빛은

   북쪽 혹은 남쪽으로 꺽이게 된다. 위에서 말했듯이, 북쪽으로 가는게 빠를지 남쪽으로 가는게 빠를지 우리가 선택해줘야 한다.

   사실 이것만 알면 되는데, 본인은 이 부분을 이해를 못해가지고 한참 애를 먹었다.

  

2) 본인은 이 문제를 BFS를 이용해서 접근해보았다. 모든 정점으로 향해보면서, 거울을 설치했을 때는 빛이 바뀔 수 있는

   모든 방향을 다 탐색해 주었다. 여기서 우리가 알 수 있는 것이, 이 문제에서는 빛이 나아가는 방향에 대해서 관리해주어야

   한다는 것이다. 본인은 좌표와 방향을 함께 관리하기 위해서 구조체를 하나 선언해주었다.

typedef struct

{

int x;

int y;

int Dir;

}Pos;

   그럼 BFS를 실행시키기 위한 초기 단계가 무엇인지 생각해보자. 시작점으로 잡혀있는 문이 하나 있을 것이다.

   그 문에서의 빛의 가장 첫 진행방향은 무엇일까?? 우리는 이 방향을 알 수 없기 때문에 4방향(동서남북) 모두에 대해서

   탐색을 해줘야 한다.

   본인은 Queue에서 관리하는 자료형을 Pos로 설정해주었는데(위의 구조체), 초기 Queue의 원소로는

   시작점 + 동, 서, 남, 북 이렇게 4가지 값을 원소로 집어 넣어주고 탐색을 시작하였다.

   또한, 중복된 탐색을 방지하기 위해서 Visit[][][4] 3차원배열을 사용하였다. 3차원 배열을 사용한 이유는, 같은 좌표에 있더라도

   빛의 진행방향에 따라 결과가 달라지기 때문이다.

   예를 들어서, (A, B)라는 좌표에서 동쪽으로 빛이 움직이고 있을 때, (A, B)를 만나는 것과, 북쪽으로 움직이고 있을 때, (A, B)를

   만나는 것은 같은(A, B)에서 만나는 것이지만, 빛의 방향에 따라 서로 다른 값을 가질 수 있기 때문에 3차원 배열을 사용해 주었

   다. Visit[A][B][C] = D의 의미는 "(A,B)에서 빛이 C방향으로 진행하고 있을 때, 지금까지 설치한 문의 갯수는 D개입니

   다." 가 된다.

  

3) 탐색을 할 때 조건에 대해서 알아보도록 하자.

   - 맵에서 '.' 으로 표시된 정점을 만났을 경우

     - '.'으로 표시된 정점은 빛이 그냥 투과할 수 있는 지점이다. 빛이 못가지도 않고, 방향이 바뀌지도 않는 그런 정점이기 때문에

       현재 설치한 거울의 갯수를 그대로 유지해 주면서, 계속해서 진행해주면 된다.

   - 맵에서 '!' 로 표시된 정점을 만났을 경우

     - '!'로 표시된 정점은 거울을 설치할 후보 지점이다. 즉, 거울을 설치해도 되고, 거울을 설치하지 않아도 된다.

       거울을 설치하는 경우에는 현재 빛의 방향을 고려해서, 꺽일 수 있는 모든 빛의 방향에 대해서 모두 탐색, 진행해주면 된다.

       물론, 거울을 설치했으므로 현재까지 설치한 거울의 갯수도 ++ 시켜줘야 한다.

       반대로, 거울을 설치하지 않아도 된다. 거울을 설치하지 않을 경우 '.'과 똑같은 역할을 하는 정점이 된다.

   - 맵에서 '*'로 표시된 정점을 만났을 경우

     - 이 정점은 탐색을 할 수 없는 정점이다.

4) 위와 같이 모두 탐색을 진행했으면 이제 마지막 정답을 도출하는 과정이다. 정답도 한번에 도출해내는 것이 아닌, 모든 방향에

   대해서 비교를 해줘야한다. 동쪽으로 움직이면서 도착지에 도착한 경우, 서쪽으로..남쪽으로..북쯕으로.. 이 모든 경우가

   존재할 수 있기 때문이다.

   즉, Visit[도착점.x][도착점.y][동/서/남/북] 중에서 최소값을 찾아서 도출하면 그게 정답이 된다 !

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 50
#define INF 987654321
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int Dir;
}Pos;
 
int N, Answer;
char MAP[MAX][MAX];
int Visit[MAX][MAX][4];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
pair<int, int> Start, End;
queue<Pos> Q;
 
void Input()
{
    int Tmp = 0;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == '#')
            {
                if (Tmp == 0)
                {
                    Start.first = i;
                    Start.second = j;
                    Tmp++;
                }
                else
                {
                    End.first = i;
                    End.second = j;
                }
            }
            Visit[i][j][0] = Visit[i][j][1] = Visit[i][j][2] = Visit[i][j][3] = INF;
        }
    }
}
 
pair<int, int> Change_Direct(int Cur_Dir)
{
    pair<int, int> R;
    if (Cur_Dir == 0 || Cur_Dir == 1)
    {
        R.first = 2;
        R.second = 3;
    }
    else if (Cur_Dir == 2 || Cur_Dir == 3)
    {
        R.first = 0;
        R.second = 1;
    }
    return R;
}
 
void BFS()
{
    while (Q.empty() == 0)
    {
        int x = Q.front().x;
        int y = Q.front().y;
        int dir = Q.front().Dir;
        Q.pop();
 
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        pair<int, int> nd = Change_Direct(dir);
 
        if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
 
        if (MAP[nx][ny] == '*') continue;
        else if (MAP[nx][ny] == '!')    // 거울을 설치할 수 있는 지점이라면
        {
            if (Visit[nx][ny][dir] > Visit[x][y][dir]) // 거울설치 X
            {
                Visit[nx][ny][dir] = Visit[x][y][dir];
                Pos Temp;
                Temp.x = nx;
                Temp.y = ny;
                Temp.Dir = dir;
                Q.push(Temp);
            }
 
            if (Visit[nx][ny][nd.first] > Visit[x][y][dir] + 1)
            {
                Visit[nx][ny][nd.first] = Visit[x][y][dir] + 1;
                Pos Temp;
                Temp.x = nx;
                Temp.y = ny;
                Temp.Dir = nd.first;
                Q.push(Temp);
            }
 
            if (Visit[nx][ny][nd.second] > Visit[x][y][dir] + 1)
            {
                Visit[nx][ny][nd.second] = Visit[x][y][dir] + 1;
                Pos Temp;
                Temp.x = nx;
                Temp.y = ny;
                Temp.Dir = nd.second;
                Q.push(Temp);
            }
        }
        else if (MAP[nx][ny] == '.')
        {
            if(Visit[nx][ny][dir] > Visit[x][y][dir])
            {
                Visit[nx][ny][dir] = Visit[x][y][dir];
                Pos Temp;
                Temp.x = nx;
                Temp.y = ny;
                Temp.Dir = dir;
                Q.push(Temp);
            }
        }
        else if (MAP[nx][ny] == '#')
        {
            if (Visit[nx][ny][dir] > Visit[x][y][dir])
            {
                Visit[nx][ny][dir] = Visit[x][y][dir];
            }
        }
    }
}
 
 
void Solution()
{
    for (int i = 0; i < 4; i++)
    {
        Pos Temp;
        Temp.x = Start.first;
        Temp.y = Start.second;
        Temp.Dir = i;
        Q.push(Temp);
        Visit[Start.first][Start.second][i] = 0;
    }
    BFS();
 
    int Answer = INF;
    for (int i = 0; i < 4; i++)
    {
        if (Answer > Visit[End.first][End.second][i])
        {
            Answer = Visit[End.first][End.second][i];
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}