백준 6087 - 레이저 통신

문제 설명

크기가 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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 두 개의 C를 연결하는데 선이 꺾이는 횟수를 최소로 만드는 것이다.

 

보통의 BFS를 사용하면 꺾이는 횟수를 카운팅하며 방문여부를 확인하는데 메모리 초과가 발생한다.

bool 자료형으로 해당하는 위치에 방문여부를 확인하면 오래 걸리더라도 적게 꺾이는 경로가 무시된다.

따라서, 다른 방법의 BFS를 적용해야 한다.

 

0-1 BFS를 적용하면 문제를 풀 수 있다.

문제의 목적은 거울을 최소한으로 설치하는 것이다.

즉, 거울이 적게 드는 경로를 우선으로 판단하면 된다.

 

예를 들어 보자.

노란 부분에서 초록 부분으로 이동하는 과정에서 왼쪽으로 이동하는 경로는 거울을 사용하지 않는다.

하지만, 위, 아래로 이동하는 경로는 거울을 설치해야 한다.

따라서, 왼쪽으로 이동하는 경로는 deque의 앞쪽에 위, 아래쪽으로 이동하는 경로는 deque의 뒤쪽에 삽입하여 처리하면 된다.

if (i == dir) dq.push_front({ { newY, newX }, i, mirror });
else dq.push_back({ {newY, newX}, i, mirror + 1 });

 

이 문제에서 가장 중요한 부분은 방문 여부를 확인하는 것이다.

방문 여부를 확인하면 시간이 오래 걸리는 경로가 무시되고, 방문 여부를 확인하지 않으면 메모리 초과가 발생한다.

이는 DP와 비슷하게 해결할 수 있다.

해당 위치에 도달하기까지 설치한 거울의 개수를 기록하여 더 많은 거울이 필요한 경로는 제외한다.

if (visited[newY][newX] <= mirror) continue;

 

BFS를 진행하다 목적지에 도달했다면 정답을 갱신하면 된다.

if (newY == End.first && newX == End.second)
{
    if (i == dir) answer = min(answer, mirror);
    else answer = min(answer, mirror+1);
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;

int N, M;

vector<int> dy = { 0, -1, 0, 1 };
vector<int> dx = { -1, 0, 1, 0 };

enum DIR
{
    LEFT,
    UP,
    RIGHT,
    DOWN
};


int BFS(vector<vector<char>>& LaserMap, vector<pair<int, int>>& Targets)
{
    pair<int, int> Start = Targets[0];
    pair<int, int> End = Targets[1];

    int answer = INT_MAX;

    //pos, dir, mirror
    deque<tuple<pair<int, int>, int, int>> dq;

    vector<vector<int>> visited(N, vector<int>(M, INT_MAX));
    visited[Start.first][Start.second] = 0;

    for (int i = 0; i < 4; i++)
    {
        int newY = Start.first + dy[i];
        int newX = Start.second + dx[i];

        if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue;
        if (LaserMap[newY][newX] == '*') continue;
        if (newY == End.first && newX == End.second) return 0;

        visited[newY][newX] = 0;
        dq.push_back({ {newY,newX}, i, 0});
    }


    while (!dq.empty())
    {
        auto [pos, dir, mirror] = dq.front();
        dq.pop_front();

        visited[pos.first][pos.second] = min(visited[pos.first][pos.second], mirror);

        for (int i = 0; i < 4; i++)
        {
            int newY = pos.first + dy[i];
            int newX = pos.second + dx[i];

            if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue;
            if (LaserMap[newY][newX] == '*') continue;
            if (visited[newY][newX] <= mirror) continue;
            if (newY == End.first && newX == End.second)
            {
                if (i == dir) answer = min(answer, mirror);
                else answer = min(answer, mirror+1);
            }

            if (i == dir) dq.push_front({ { newY, newX }, i, mirror });
            else dq.push_back({ {newY, newX}, i, mirror + 1 });
        }
    }

    return answer;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> M >> N;

    vector<vector<char>> LaserMap(N, vector<char>(M));
    vector<pair<int, int>> Targets;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> LaserMap[i][j];
            if (LaserMap[i][j] == 'C')
            {
                Targets.push_back({ i,j });
            }
        }
    }
    
    cout << BFS(LaserMap, Targets);

	return 0;
}

---