[ 백준 6087 ] 레이저 통신 (C++)

백준의 레이저통신(6087) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 먼저 문제를 풀기전에 주의해야 할 점에 대해서 생각해보자. 우리는 이 문제를 풀 때, 방향이 꺾이는 과정일 때 무언가를

   해줘야 한다. 방향이 꺾인다는 것은 그 곳에 거울을 설치한다는 말이고, 이 거울의 갯수를 관리해줄 수 있는 무언가가

   필요하다.

   그리고 무작정 상하좌우 4방향으로 진행시키는 것이 아니라, 진행방향과 그 다음 향할 방향에 대해서도 관리해주어야

   한다. 예를 들어서 현재 동쪽으로 나아가는데, 그 다음칸에서 동쪽으로 진행한다면, 이 경우에는 거울 없이 나아갈 수

   있지만, 북쪽이나 남쪽으로 진행하게 된다면 거울이 필요하기 때문이다.

2) 본격적으로 문제를 풀어보자. 본인은 BFS로 해결하였는데, Queue에서는 총 4개의 변수를 관리해 주었다.

   {{ x좌표, y좌표 } , { 현재진행방향, 놓은거울의갯수}} 이렇게 총 4개의 변수를 관리해 주었다.

   또한, 각 좌표별로 갈 수 있는 최소의 거울 갯수를 Visit[][] 2차원 배열에 저장해주었다.

   즉, 우리는 모든 좌표를 탐색해보고, Visit[마지막좌표.x][마지막좌표.y] 의 값을 출력시키면 되는 것이다.

3) Queue에 가장 처음에는 4개의 값을 넣는다. 시작 x,y 좌표와 현재 진행방향을 동서남북 4가지 방향에 대해서

   모두 넣어주고 시작한다. BFS를 진행할 때 생각해야될 조건이 하나 있다. 이 조건을 포함해서 모든 조건을 한번

   알아보자.

   1. 탐색하고자 하는 좌표가 맵의 범위 내인지

   2. 탐색하고자 하는 좌표가 맵에서 갈 수 있는 곳인지.

   사실상 위의 2개의 조건은 너무나 기본적인 조건이다.

   3. 현재 진행방향과 다른 방향으로 나아가는지?

   4. 탐색하고자 하는 좌표의 거울의 갯수와 현재 놓은 거울의 갯수보다 더 큰지 작은지?

  

   3번을 위해서 우리는 Queue에 현재 진행방향을 넣어두었다.

   우리는 일반적으로 for(int i = 0 ; i < 4; i++) nx = x + dx[i] ; ny = y + dy[i]; 이런식으로 방향전환을 표현한다.

   이 때, Queue에서 나온 현재 진행방향과 i 값을 비교해서 다르다면 해당 좌표에는 거울을 놓아야 한다는 의미로 거울의

   갯수를 ++해주어야 한다.

   또한, 4번의 조건문을 만족시키기 위해서 탐색하고자 하는 좌표의 지금까지의 거울갯수와, 우리가 거울을 놓을지 안놓을지

   는 모르지만, 거울의 갯수를 비교해서 현재 거울의 갯수가 지금까지의 거울 갯수보다 작다면 갱신해주고 Queue에 다시

   넣어주었다.

   위의 설명을 그림을 통해서 구체적으로 알아보자.

  

   시작점에서 A까지 가정해보자. A까지 가는방법으로는 3가지 방법이 있다.

   방법1. 시작점 → A

   방법2. 시작점 → B → C → A

   방법3. 시작점 → B → C → E →D → A

   우리는 "지금까지의 거울 갯수와 현재 우리가 거울을 놓을지 안놓을지 모르는 거울의 갯수와 비교해서 현재 거울의

   갯수가 지금까지의 거울 갯수보다 작으면 갱신" 이라고 알고있다.

   말 그대로 접근해보자.

   방법1의 경우 거울이 A까지 가는데 총 0개가 필요하다.

   즉, A좌표의 현재 까지의 거울 갯수는 0개 가 된다.

   방법2를 통해서 가보자. 시작점 → B → C 과정에서 거울이 1개 필요하다. (진행방향이 남쪽 → 동쪽으로 바뀌므로)

   또 C → A에서 거울이 1개 필요하다. (진행방향이 동쪽 → 북쪽으로 바뀌므로)

   총 거울이 2개가 필요하다.

   그렇다면, 이 때 A좌표의 지금까지의 거울 갯수와, 현재 거울 갯수를 비교하는 것이다.

   지금까지의 거울 갯수 = 0 개

   현재 거울 갯수 = 2개 이므로 거울의 갯수는 0개로 유지된다.

   방법3을 통해서 접근하더라도 똑같은 결과가 일어나게 된다.

4) 우리는 이제 거울을 놓는 방법까지 알았다. 마지막으로 주의해야 할 부분은 우리가 가고자 하는 좌표에 도착했다고

   그대로 Queue의 반복을 끝내버리면 안된다. 우리가 좌표에 도착했다고 끝내버리는 것은 최단거리를 구할 때이다.

   이 문제는 최단거리가 아닌, 거울의 갯수를 최소화 시키는 것이 문제이다.

  

   이런 맵이 있다고 가정해보자. 우리는 시작점에서 도착점까지 갈 수 있는 여러가지 방법이 있다.

    그 중에

    방법 1. 시작점 → A → D → E → 도착점 으로 가는 방법과

    방법 2. 시작점 → A → B → E → 도착점 으로 가는 방법 2가지만 비교해보겠다.

    방법 1의 경우 시작점에서 진행방향을 동쪽으로 설정할 경우,

    A → D , D → E , E → 도착점 으로 방향을 전환해야 하므로 총 거울이 3개 필요하다.

    하지만 방법 2의 경우 시작점에서 진행방향을 동쪽으로 설정할 경우 B → E 로 전환하는 거울이 1개만 필요하다.

    즉, 방법1과 방법2 모두 4초가 걸리는 것은 똑같지만 방법2가 거울의 갯수를 더욱 최소화 할 수 있다는 것이다.

    그러므로 방법 1의 루트로 도착점에 도착했다고 반복을 끝내버리면 잘못된 정답이 출력될 것이다.

    따라서, Queue가 모두 진행될 때 까지 중간에 종료해주는 부분은 없어야 한다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int W, H;
char MAP[MAX][MAX];
int Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
pair<int, int> Start, End;
 
void Input()
{
    int Tmp = 0;
    cin >> W >> H;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'C')
            {
                if (Tmp == 0)
                {
                    Start.first = i;
                    Start.second = j;
                    Tmp++;
                }
                else
                {
                    End.first = i;
                    End.second = j;
                }
            }
            Visit[i][j] = 987654321;
        }
    }
}
 
int BFS(int a, int b)
{
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    for (int i = 0; i < 4; i++)
    {
        Q.push(make_pair(make_pair(a, b), make_pair(i, 0)));
    }
    Visit[a][b] = 0;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Dir = Q.front().second.first;
        int Cnt = Q.front().second.second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nCnt = Cnt;
 
            if (nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
            if (MAP[nx][ny] == '*') continue;
            if (Dir != i) nCnt = nCnt + 1;
            if (Visit[nx][ny] >= nCnt)
            {
                Visit[nx][ny] = nCnt;
                Q.push(make_pair(make_pair(nx, ny), make_pair(i, nCnt)));
            }
        }
    }
    return Visit[End.first][End.second];
}
 
void Solution()
{
    int R = BFS(Start.first, Start.second);
    cout << R << 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;
}