Baekjoon 2151번 거울 설치

문제

https://www.acmicpc.net/problem/2151

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<pair<int, int>> door;
vector<vector<char>> house;
vector<vector<vector<int>>> visited;

struct light{
    int y;
    int x;
    int d; // direction
    int m; // mirror
    light(int y, int x, int d, int m){
        this->y = y;
        this->x = x;
        this->d = d;
        this->m = m;
    }
};

int bfs(){
    int sy = door[0].first;
    int sx = door[0].second;
    int ey = door[1].first;
    int ex = door[1].second;
    visited.resize(4, vector<vector<int>>(n, vector<int>(n, 0)));    
    queue<light> q;
    for(int i = 0; i < 4; i++){
        int ny = sy+dy[i];
        int nx = sx+dx[i];
        if(0 <= ny && ny < n && 0 <= nx && nx < n){
            if(house[ny][nx] != '*'){
                visited[i][sy][sx] = 1;
                q.push(light(sy, sx, i, 0));
            }
        }
    }
    while(!q.empty()){
        int y = q.front().y;
        int x = q.front().x;
        int d = q.front().d;
        int m = q.front().m;
        q.pop();
        // 현재 방향으로 빛이 진행
        int ny = y, nx = x;
        while(true){
            ny += dy[d];
            nx += dx[d];
            if(0 > ny || n <= ny || 0 > nx || n <= nx || house[ny][nx] == '*') break;
            if(ny == ey && nx == ex) return m;
            if(house[ny][nx] == '!'){
                // 거울을 두가지 대각선 방향으로 각각 설치하는 경우
                if(0 <= d && d < 2){
                    for(int i = 2; i < 4; i++){
                        if(!visited[i][ny][nx]){
                            visited[i][ny][nx] = 1;
                            q.push(light(ny, nx, i, m+1));
                        }
                    }
                }
                else{
                    for(int i = 0; i < 2; i++){
                        if(!visited[i][ny][nx]){
                            visited[i][ny][nx] = 1;
                            q.push(light(ny, nx, i, m+1));
                        }
                    }
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    house.resize(n, vector<char>(n));
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n; x++){
            cin >> house[y][x];
            if(house[y][x] == '#')
                door.push_back(make_pair(y, x));
        }
    }
    cout << bfs();
    return 0;
}

문제는 한쪽 문에서 다른 쪽 문이 보이도록 거울을 설치할 때, 설치해야 하는 거울의 최소 개수를 구하려고 한다.

방향이 같은 두 빛이 거울을 설치할 수 있는 같은 좌표에 도착하였을 때, 먼저 도착한 빛의 경로가 반드시 최적이기 때문에 bfs 탐색을 사용하였다.

1. 집의 정보가 주어질 때 문의 좌표를 저장하고 하나의 문으로부터 진행될 수 있는 빛의 방향을 찾아낸다.
2. 현재 빛의 방향으로 쭉 나아가다 거울을 설치할 수 있는 위치를 만나면 두 대각선 방향으로 거울을 설치했을 때 바뀌는 빛의 진행 방향을 queue 에 추가한다.
3. 빛이 진행하다 다른 문을 만나면 지금까지 설치한 거울의 개수를 return 한다.

거울을 설치할 수 있는 각 좌표마다 바뀔 수 있는 방향의 개수는 4개이므로 4xNxN 3차원 방문 배열을 사용하여야 하고, queue 포함되어야 할 값은 현재 좌표와 방향, 설치한 거울의 개수 4가지 값이 필요하다.

맨 처음 문으로부터 진행될 수 있는 빛의 방향을 찾아낼 때 벽이 아닌 모든 값은 빛이 이동할 수 있는 경로이지만, 아무것도 없는 위치 . 와 거울을 설치할 수 있는 위치인 ! 만을 이동할 수 있는 방향으로 queue 에 추가하는 바람에 100% 에서 틀렸습니다 가 출력되었다.

질문 글을 보니 똑같은 문제로 올라와 있는 글이 있어 바로 수정했다. 조금 더 꼼꼼해야 할 필요가 있다...