[BOJ/C++] 백준 2151 - 거울 설치

 

👻 문제 설명

BFS문제이지만, 인접한 칸으로 이동하는 기존 문제와 다르게 90도로 이동해야 하는 점 + 거울을 설치할 수 있는 곳까지 연속으로 쭉 이동해야하는 점이 달랐습니다. 이 점을 유의해서 BFS 코드를 조금 고쳐서 풀어보았습니다 : )

😔 해결 과정

편의 상, 시작점 (#)에서 도착점(#) 까지 '빛이 이동한다'라고 표현하겠습니다.

BFS를 수행하는 목적은, 빛이 시작점에서 도착점까지 이동하였을 때 '거울이 최소 몇 번 사용되느냐' 입니다. 이 말은 즉, '빛이 최소 몇 번 꺾이느냐'를 의미합니다. 따라서 거울을 놓을 수 있는 모든 위치에 대해서, 빛이 꺾일 수 있는 다음 위치를 모두 찾아 이동하는 것을 시뮬레이션하고 도착점(#)에 도달하였을 때 사용한 거울의 최솟값을 구하면 됩니다.

이 때 유의해야할 것은, 기존에는 visited 이차원 배열로 왔던 곳에 또 오는 경우를 예외처리했었지만 이번에는 같은 칸에 도달하더라도 어느 방향으로 이동하다가 도달하였는지, 그리고 지금껏 사용한 거울은 몇 개인지에 따라 앞으로의 최소 횟수가 달라지기 때문에 조금 더 다른 방법으로 캐싱해주어야 합니다.

BFS 수행 과정을 통해 자세하게 설명하겠습니다.

(1) 제일 처음, 시작점(#) 에서 출발할 때는 네 방향으로 빛이 퍼져 나간다.

    queue<tuple<int, int, int, int>> q; // y, x, direction, mirror
    q.push(make_tuple(sy, sx, 0, 0));
    q.push(make_tuple(sy, sx, 1, 0));
    q.push(make_tuple(sy, sx, 2, 0));
    q.push(make_tuple(sy, sx, 3, 0));

(2) 각 방향에서 이동할 수 있는 다음 위치(!)를 쭉 탐색한다.

while (!q.empty()) {
        int y, x, direction, mirror;
        tie(y, x, direction, mirror) = q.front(); q.pop();

        int ny = y + dy[direction], nx = x + dx[direction];
        while (true) {
            if (isOut(ny, nx) || board[ny][nx] == '*') break;
            ....

(3) 거울을 둘 수 있는 곳(!)이 나왔을 때, 이동하던 방향이 왼쪽, 혹은 오른쪽이면 90도를 회전하여 위, 혹은 아래로 방향이 꺾일 수 있고 이동하던 방향이 위, 혹은 아래라면 왼쪽, 혹은 오른쪽으로 꺾일 수 있다. 그리고, 거울을 설치하지 않고 넘어갈 수도 있으므로 이동하던 방향으로 계속 진행할 수 있다.

if (board[ny][nx] == '!') { // 중복 방문한 경우 예외처리
    if (check[ny][nx][direction][mirror]) break;
    check[ny][nx][direction][mirror] = true;
    if (direction == 0 || direction == 1) {
        q.push(make_tuple(ny, nx, 2, mirror + 1));
        q.push(make_tuple(ny, nx, 3, mirror + 1));
    }
    else {
        q.push(make_tuple(ny, nx, 0, mirror + 1));
        q.push(make_tuple(ny, nx, 1, mirror + 1));
    }
    q.push(make_tuple(ny, nx, direction, mirror));
    break;
}

이렇게 하면, 거울을 둘 수 있는 곳(!) 이 발견되었을 때 큐에는 총 세가지 경우의 수가 저장이 된다.

(4) 만약 진행하다 도착점을 발견한 경우, 그 때 사용한 거울을 배열에 넣고 종료한다.

if (ny == ey && nx == ex) { // 목적지에 도착한 경우
        candidates.push_back(mirror);
        break;
    }

이제 candidates 배열의 최솟값을 구하여 반환하면 정답을 구할 수 있습니다.

🔥 소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <tuple>
using namespace std;

int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, 1, -1 };

int n;
bool check[51][51][4][2501];

vector<string> board;
vector<int> candidates;
int sy = -1, sx, ey, ex;

bool isOut(int y, int x) {
    return y < 0 || y >= n || x < 0 || x >= n;
}

void bfs() {
    memset(check, false, sizeof(check));
    queue<tuple<int, int, int, int>> q; // y, x, direction
    q.push(make_tuple(sy, sx, 0, 0));
    q.push(make_tuple(sy, sx, 1, 0));
    q.push(make_tuple(sy, sx, 2, 0));
    q.push(make_tuple(sy, sx, 3, 0));

    while (!q.empty()) {
        int y, x, direction, mirror;
        tie(y, x, direction, mirror) = q.front(); q.pop();

        int ny = y + dy[direction], nx = x + dx[direction];
        while (true) {
            if (isOut(ny, nx) || board[ny][nx] == '*') break;
            if (board[ny][nx] == '!') { // 중복 방문한 경우 예외처리
                if (check[ny][nx][direction][mirror]) break;
                check[ny][nx][direction][mirror] = true;
                if (direction == 0 || direction == 1) {
                    q.push(make_tuple(ny, nx, 2, mirror + 1));
                    q.push(make_tuple(ny, nx, 3, mirror + 1));
                }
                else {
                    q.push(make_tuple(ny, nx, 0, mirror + 1));
                    q.push(make_tuple(ny, nx, 1, mirror + 1));
                }
                q.push(make_tuple(ny, nx, direction, mirror));
                break;
            }
            if (ny == ey && nx == ex) { // 목적지에 도착한 경우
                candidates.push_back(mirror);
                break;
            }
            ny += dy[direction], nx += dx[direction];
        }
    }
}


int main() {
    cin >> n;
    board = vector<string>(n);
    for (int i = 0; i < n; i++) {
        cin >> board[i];
        for (int j = 0; j < n; j++)
            if (sy == -1 && board[i][j] == '#')
                sy = i, sx = j;
            else if (board[i][j] == '#')
                ey = i, ex = j;
    }

    bfs();
    int ret = -1;
    for (int i = 0; i < candidates.size(); i++)
        if (ret == -1 || ret > candidates[i]) ret = candidates[i];
    cout << ret << endl;
    return 0;
}

👍 고찰

또 다른 풀이 방법으로는, 주어진 입력에서 거울을 둘 수 있는 곳에 번호를 매기고, 모든 위치에서 다른 위치로의 이동 가능 여부를 저장합니다. (canGo 배열)

그 다음, BFS 코드에서 네 방향을 검사하는 대신, 다음으로 이동할 모든 위치를 검색하며 이동할 수 있다면 현재 위치에 거울을 두고 그 곳으로 이동하는 방법입니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, 1, -1 };

int n;

bool isOut(int y, int x) {
    return y < 0 || y >= n || x < 0 || x >= n;
}

int main() {
    cin >> n;
    vector<string> board(n);
    vector<vector<int>> num(n, vector<int>(n)); // point to number
    vector<pair<int, int>> point; // number to point

    int start = -1, end = -1; 
    for (int i = 0; i < n; i++) {
        cin >> board[i];
        for (int j = 0; j < n; j++) { // check visiting point
            if (board[i][j] == '#') {
                if (start == -1) start = point.size();
                else end = point.size(); 
                num[i][j] = point.size();
                point.emplace_back(i, j);
            }
            else if (board[i][j] == '!') {
                num[i][j] = point.size();
                point.emplace_back(i, j);
            }
        }
    }

    int p = point.size(); 
    // canGo[i][j] = 점 i에서 점 j로 갈 수 있는지 저장
    vector<vector<bool>> canGo(p, vector<bool>(p, false)); 
    for (int i = 0; i < p; i++) {
        for (int direction = 0; direction < 4; direction++) {
            int y = point[i].first + dy[direction]; 
            int x = point[i].second + dx[direction]; 
            while (!isOut(y, x) && board[y][x] != '*') {
                if (board[y][x] == '!' || board[y][x] == '#') 
                    canGo[i][num[y][x]] = true;
                y += dy[direction], x += dx[direction]; 
            }
        }
    }

    queue<int> q; 
    vector<int> dist(p, -1); // dist of all points from 'start'
    q.push(start);
    dist[start] = 0; 
    while (!q.empty()) {
        int here = q.front(); q.pop(); 
        for(int there= 0; there < p; there++)
            if (canGo[here][there] && dist[there] == -1) {
                dist[there] = dist[here] + 1; 
                q.push(there); 
            }
    }
    cout << dist[end] - 1 << endl;
    return 0; 
}

마지막에 이동한 거리에 1을 빼는 이유는, 이동한 거리가 3이라면 시작점부터 2개의 거울을 거쳐 도착점에 온 셈입니다. 따라서 거울의 갯수를 구하기 위해 1을 빼주는 것입니다.