[BOJ] 2151번 - 거울 설치

백준 2151번 - 거울 설치

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	5965	1390	872	23.923%

문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

입력

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.

출력

첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

---

예제 입력 1

5
***#*
*.!.*
*!.!*
*.!.*
*#***

예제 출력 1

2

출처

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

2151번: 거울 설치

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

접근 방법

맨 처음 문제를 보았을 때 필요로 하는 요구조건들이 눈에 바로 보이지 않았다.

이 후, 천천히 문제를 복기하며 조건을 구체화하여 쉽게 풀 수 있었다.

 

문제를 좀 더 구체화해보자.

1. 거울은 다음과 같이 2가지 형태로 설치할 수 있다.

1

2

1번과 2번 모두 45도의 각도로 세워져 있기 때문에, 입사각과 반사각의 관계에 따라 항상 들어온 빛의 방향과 수직으로 빛이 나갈 수 밖에 없다. 빛이 들어오는 모든 케이스에 대해서 고려하는 것은 불필요하다는 것을 구현 부분에서 확인할 수 있다.

 

2. 거울을 마주치기 전 까지 빛의 방향은 바뀌지 않는다.

당연한 소리다.. 

 

3. 우리가 구하고자 하는 것은 임의의 #의 좌표에서 또 다른 #의 좌표로 도달할 수 있는 가? 에 대한 문제이다.

-> 도달 가능성을 확인하기 위해 그래프 탐색 알고리즘을 사용하는 것이 좋을 것 같다.

그중 필자는 BFS방식을 사용했다.

 

---

우리가 구하고 싶은 것은 # ~ # 로 가는 경로 중 최소의 거울을 설치하여 갈 수 있는 경로이다.

이 경로를 구하기 위해 2개의 #의 좌표 중 임의의 하나의 좌표로 부터 탐색을 진행한다.

탐색을 진행함에 따라서, 무한 루프가 발생하는 것을 방지하기 위해 visited 배열을 선언을 해주었다.

visited 배열을 단순하게 좌표를 메모하는 용도로 2차원 배열로 선언하는 순간, 문제가 발생한다.

(a, b) -> (c, d) 로 가는 경로 중 거울을 세우고 간 경로와 거울을 세우지 않고 간 경로가 다른 경우임을 항상 유의해주어야 한다.

이를 구분해주기 위해서 3차원 visited배열을 선언하였고 [y][x][거울을 세운 횟수]의 의미를 가진다.

 

또한, 탐색을 진행함에 따라서 만날 수 있는 블록의 형태는 3가지가 될 수 있다.

첫번째로, * 가 나올 경우 해당 경로로 빛이 통과할 수 없으므로 후보해가 될 수 없다. 고로, 더 이상 해당 경로로 진행 할 이유가 없다.

두번째로, # 가 나올 경우 해당 위치에 거울을 1번타입(/)으로 설치 or 2번타입(\)로 설치 or 설치하지 않고 진행 하는 경로가 존재할 수 있다. ( 각각 해당되는 빛의 방향 값에 수직인 방향에 따라 새로운 좌표로 이동한다 )

마지막으로는, .가 나오는 경우가 있을텐데 이 경우 우리가 구체화한 2번 규칙에 의해 방향성이 바뀌지 않은 상태로 진행한다.

 

다음과 같은 방법으로 탐색을 진행한다면, 가능한 모든 경로( # ~ #로 도달하는 경로 ) 중 거울의 최소 설치 횟수를 구할 수 있다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
struct Elem{
    int y, x, d, cnt;
};
int N;
char house[51][51];
const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> N ;
    pair<int ,int> pos;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) {
            cin >> house[i][j];
            if( house[i][j] == '#' ){
                pos.first = i, pos.second = j;
            }
        }
    }

    int answer = 1e9;
    // !위치에 거울을 설치해본다.
    // {y, x, 현재 빛의 방향, 거울 설치 개수}
    queue<Elem> Q;
    bool visited[51][51][2501] = {false, };
    for(int i=0; i<4; i++) {
        Q.push({pos.first, pos.second, i, 0});
        visited[pos.first][pos.second][0] = true;
    }

    while(!Q.empty()){
        Elem fr = Q.front(); Q.pop();
        int y = fr.y, x = fr.x, d = fr.d, cnt = fr.cnt;

        // DEBUG
        // cout << "y : " << y << ", x : " << x << ", d : " << d << ", cnt : " << cnt << '\n';

        // 현재 위치가 시작점이 아니면서 #에 도달할 수 있는 경로가 존재한다? = 후보 해
        if( (y != pos.first || x != pos.second) && house[y][x] == '#' )
            answer = min(answer, cnt);

        if( house[y][x] == '*' )
            continue;
        else if( house[y][x] == '!' ){
            // 거울을 설치해본다.
            int nd1 = (d+1)%4;
            int nd2 = (d-1) >= 0 ? d-1 : 4+(d-1);
            int ny1 = y + dir[nd1][0], nx1 = x + dir[nd1][1];
            int ny2 = y + dir[nd2][0], nx2 = x + dir[nd2][1];
            if( 0 <= ny1 && ny1 < N && 0 <= nx1 && nx1 < N && !visited[ny1][nx1][cnt+1] ){
                visited[ny1][nx1][cnt+1] = true;
                Q.push({ny1, nx1, nd1, cnt+1});
            }
            if( 0 <= ny2 && ny2 < N && 0 <= nx2 && nx2 < N && !visited[ny2][nx2][cnt+1] ){
                visited[ny2][nx2][cnt+1] = true;
                Q.push({ny2, nx2, nd2, cnt+1});
            }
        }

        // 거울을 설치하지 않고 진행해본다.
        int ny = y + dir[d][0], nx = x + dir[d][1];
        if( ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx][cnt] )
            continue;
        Q.push({ny, nx, d, cnt});

    }

    cout << answer;
    return 0;
}