문제 풀이

[백준] 2151번 거울설치

컴영 2020. 7. 17. 20:45

2151 거울 설치


문제

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

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

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

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

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


입력

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


출력

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


풀이)

문제 이해가 되지 않아서 다른 분의 풀이를 참고한 문제이다.


거울 빛 반사부분이 특히 이해가 되지 않았는데 알고보니 이러한 말이였다.


거울 설치 시 45도 기울어진 방향으로 설치하여 빛을 반사한다

= 빛이 왔던 방향의 수직방향으로 바뀐다.


(예) 빛이 오른쪽으로 가는 방향이었다면 -> 빛은 위쪽 혹은 아래쪽으로 방향 바뀜

     빛이 아래쪽으로 가는 방향이었다면 -> 빛은 왼쪽 혹은 오른쪽으로 방향 바뀜


이 성질과 빛이 처음에 상하좌우 모두 퍼질 수 있다는 점을 고려해

BFS로 각 위치 각 방향일 때의 최소 거울 개수를 구할 수 있다.


참고사항

1. 첫번째 문을 빛의 출발지, 두번째 문을 빛의 도착지라고 해준다.

   빛이 출발지에서 도착지에 도달해야 문끼리 서로 보일 수 있다는 뜻이다.

2. 첫번째 문(출발지)에서 빛이 출발할 때 4방향 모두 탐색을 진행해준다.

3. 중복되는 방문 처리 위해서 3중 배열을 사용해준다. 

   방문 위치 체크, 거울 설치 개수를 저장 : visited[y][x][상/하/좌/우]


   int visited[i][j][k] = (i,j)위치에서 방향이 k일때의 지금까지 설치한 최소 거울 개수


   + 배열의 초기값은 최대 값으로 초기화해둔다.

   + visited[출발지 y][출발지 x][상/하/좌/우] = 0으로 둔다. (출발지에서는 거울 개수 0이므로)


4. 탐색하다가

  4.1 '.'을 만났을 경우 : 빛이 통과할 수 있는 지점. 그대로 탐색 진행

  4.2 '!'을 만났을 경우 : 거울을 설치할 수 있는 지점.

  거울을 설치할 경우와 설치 안 할 경우를 모두 탐색 진행

  (설치할 경우에는 왔던 방향과 수직인 방향으로 빛의 방향을 바꾸고,

   거울 개수도 +1 해줘야 한다)

  4.3 '*'을 만났을 경우 : 빛이 통과할 수 없는 지점. 탐색 그만


5. 두번째 문 즉 빛의 도착지에서 visited[][][상/하/좌/우] 4가지 값 중 최소 거울 개수를 출력하면 된다.

   (한 쪽문에서 다른 쪽문을 볼 수 없는 경우는 주어지지 않는다고 했음)


코드)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <queue>
using namespace std;
 
#define INF 999999999
int N;
char map[50][50];
int visited[50][50][4];
pair<int, int> start, dest;
//상 0 하 1 좌 2 우 3
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct Info {
    int y, x, dir;//위치, 방향 저장하는 구조체
    Info() {}
    Info(int y, int x, int dir) {
        this->y = y;
        this->x = x;
        this->dir = dir;
    }
};
 
void bfs() {
    queue <Info> qu;
    int change_dir[2];////바뀐 방향값 저장
    //출발지에서 4방향 모두 빛 출발
    for (int i = 0; i < 4; i++) {
        visited[start.first][start.second][i] = 0;
        qu.push({ start.first,start.second,i });
    }
    
    while(!qu.empty()) {
        int y = qu.front().y;
        int x = qu.front().x;
        int dir = qu.front().dir;
        qu.pop();
 
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if (ny < 0 || ny >= N || nx < 0 || nx >= N || map[ny][nx] == '*') continue;
 
        if (map[ny][nx] == '.') {//빛이 통과할 수 있는 지점
            if (visited[ny][nx][dir] > visited[y][x][dir]) visited[ny][nx][dir] = visited[y][x][dir];
            qu.push({ ny,nx,dir });
        }
        else if (map[ny][nx] == '!') { //거울 설치 가능한 지점
            //거울 설치 x
            if (visited[ny][nx][dir] > visited[y][x][dir]) {
                visited[ny][nx][dir] = visited[y][x][dir];
                qu.push({ ny,nx,dir });
            }
            //거울 설치
            //바뀐 방향 값 확인
            if (dir == 0 || dir == 1) {//원래 방향이 상,하 이면 방향은 좌, 우로 바뀜
                change_dir[0] = 2;
                change_dir[1] = 3;
            } 
            else {
                change_dir[0] = 0;
                change_dir[1] = 1;
            } 
            
            for (int i = 0; i < 2; i++) {
                if (visited[ny][nx][change_dir[i]] > visited[y][x][dir] + 1) {
                    visited[ny][nx][change_dir[i]] = visited[y][x][dir] + 1;
                    qu.push({ ny,nx,change_dir[i] });
                }
            }
        }
        else {//도착지일 경우
            if(visited[ny][nx][dir] > visited[y][x][dir]) visited[ny][nx][dir] = visited[y][x][dir];
        }
 
    }
 
}
 
int main() {
    scanf("%d", &N);
    getchar();
    bool find = false;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < 4; k++) visited[i][j][k] = INF;//최대값으로 초기화
            scanf("%c", &map[i][j]);
            if (map[i][j] == '#') {
                if (find) {//두번째 문 즉 도착지 발견
                    dest.first = i;
                    dest.second = j;
                }
                else {//첫번째 문 즉 출발지 발견
                    start.first = i;
                    start.second = j;
                    find = true;
                }
            }
        }
        getchar();//공백처리
    }
    bfs();
    int result = INF;
    for (int i = 0; i < 4; i++) {
        if (result > visited[dest.first][dest.second][i]) result = visited[dest.first][dest.second][i];
    }
    printf("%d", result);
    return 0;
}
cs


저작자표시 비영리 변경금지 (새창열림)