[백준 6087] - 레이저 통신(C++)[골드3]

문제

크기가 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를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

🔎문제 해석

문제가 길고 그림이 복잡해보이지만, BFS 알고리즘을 사용해서 최솟값을 구하는 문제입니다.
이러한 유형은 반복된 유형을 풀어보는것만이 방법입니다.

 

우선 상위티어 BFS/DFS 문제는 3차원 배열을 사용해서 값을 추가로 하나 더 기록하는 방법을 사용하는 문제가 아주 많습니다.

예를 들어 방향을 저장하던가, 방향에 대한 값을 저장하던가, 이러한 식으로 3차원 배열을 사용해서 이전 방향에 대한 값을 저장해야 합니다.

 

지금도 저희는 도착지점까지의 최소 거울의 개수를 필요로 하기에, 3차원 배열에 각 진행방향 별로 거울의 개수를 저장해 줍니다.

 

예를 들어서

(X, Y) -> (A, B)로 이동을 하는 시점에서, 만약 방향을 바꾼다면, 거울을 하나 추가해줘야 합니다.

따라서 (A, B, 바뀐 방향) = (X, Y, 기존방향)+1이 답일 것입니다.

(X, Y) -> (A, B)로 이동을 하는 시점에서 , 만약 방향을 바꾸지 않는다면, 거울의 개수는 변동이 없습니다.

따라서 (A, B, 기존방향) = (X, Y, 기존방향) 일 것입니다.

그리고 저희는 항상 거울을 최소로 필요로 하기에, 방문할 때마다 비교를 해줘서 거울을 업데이트해줘야 하며 

도착지점에 도착 시 최솟값을 저장합니다.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
int w, h;
vector<vector<char> > graph;
vector<pair<int, int> > answer;
queue<pair<pair<int, int>, int> > q;
vector<vector<vector<int> > > v;
void funct();
int Move[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int ans = INT_MAX;
int main()
{
    cin >> h >> w;
    graph.resize(w, vector<char>(h, 0));
    v.resize(w, vector<vector<int> >(h, vector<int>(4, INT_MAX))); // w*h*4 배열
    for (int i = 0; i < w; i++)
    {
        for (int j = 0; j < h; j++)
        {
            cin >> graph[i][j];
            if (graph[i][j] == 'C')
                answer.push_back(make_pair(i, j));
        }
    }
    funct();
    cout << ans<< endl;
}
void funct()
{
    q.push(make_pair(make_pair(answer[0].first, answer[0].second), 0)); // 레이저 좌표와 모든 방향을 넣어줌.
    q.push(make_pair(make_pair(answer[0].first, answer[0].second), 1));
    q.push(make_pair(make_pair(answer[0].first, answer[0].second), 2));
    q.push(make_pair(make_pair(answer[0].first, answer[0].second), 3));
    for (int i = 0; i < 4; i++) //초기 출발점은 0으로 세팅한다.
    {
        v[answer[0].first][answer[0].second][i] = 0;
    }
    while (!q.empty())
    {
        auto loc = q.front().first; //x,y 좌표
        int dir = q.front().second; //방향
        if (loc.first == answer[1].first && loc.second == answer[1].second) //도착지점에 도착한다면 최소값을 기록.
        {
            ans=min(ans,v[loc.first][loc.second][dir]);
        }
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int temprow = loc.first + Move[i][0];
            int tempcol = loc.second + Move[i][1];
            if (temprow < 0 || tempcol < 0 || temprow >= w || tempcol >= h) //배열을 넘어가는 경우
                continue;
            if (graph[temprow][tempcol] == '*') //벽에 막힌 경우
                continue; 
            if (i != dir) //방향이 다를 경우 : 거울을 추가해야함.
            {
                if (v[temprow][tempcol][i] > v[loc.first][loc.second][dir] + 1)
                {
                    v[temprow][tempcol][i] = v[loc.first][loc.second][dir] + 1;
                    q.push(make_pair(make_pair(temprow, tempcol), i));
                }
            }
            else //방향이 같을 경우 : 거울을 추가 안해도 됨.
            {
                if(v[temprow][tempcol][i]>v[loc.first][loc.second][dir])
                {   
                    v[temprow][tempcol][i] = v[loc.first][loc.second][dir];
                    q.push(make_pair(make_pair(temprow, tempcol), i));
                }
            }
        }
    }
}

 

😀느낀 점

• 상위 티어 BFS 문제를 풀어보면 알 수 있듯이, 단순히 탐색하는 거에 지치지 않고, 고차원 배열을 사용해서 값을 기록하는 방식의 풀이법이 많은 것 같다.
• BFS 문제는 반복하면 눈에 익히고, 코드도 손에 익는 것 같다.