본문 바로가기

공부/알고리즘 문제풀이

[삼성 기출 문제] 백준 15683 감시

반응형

문제 링크


어떻게 풀까?


이 문제는 여러 개의 카메라를 돌려서 카메라의 영역에 들어오지 않는 부분(사각 지대)을 찾는 문제입니다.

시뮬레이션이면서 완전 탐색의 성격을 모두 갖추고있죠!


카메라를 돌리는 것에서 다양한 방법이 있을 수 있습니다.

문제를 풀기전에


1. 카메라를 어떻게 돌릴지, 

2. 카메라가 비추는 영역을 어떻게 표시할지 


에 대해서 생각해 봅시다.


첫 번째로, 카메라를 어떻게 돌릴까? 입니다.



보시면, 카메라는 총 5가지 종류가 있습니다.

1번 카메라는 90도씩 돌린다고 하면 총 4개의 다른 부분을 보는 영역을 만들 수 있겠죠!




이렇게 4개의 방향을 만들 수 있죠!

이와 비슷하게 2번은 2개, 3번은 4개, 4번도 4개, 5번은 1개의 서로 다른 방향을 만들 수 있습니다. (csize)

또한, 화살표의 갯수는 1번 - 1개, 2번 - 2개, 3번 - 2개, 4번 - 3개, 5번 - 4개 입니다. (dcnt)


그럼, 회전하는 것은 어떻게 만들 수 있을까요?


0번 - 상

1번 - 우

2번 - 하

3번 - 좌


라고 해 봅시다.


이렇게 해놓으면, 90도를 돌리는 것은  (x+1)%4 번 인 것을 알 수 있습니다!



그림으로 보면 다음과 같겠죠!


카메라를 돌리는 방법은,

카메라가 회전해서 만들 수 있는 서로 다른 방향(csize)만큼 

카메라의 화살표들에 +1을 계속 해주면 되는 것입니다!!


2번 카메라를 270도 회전하는 경우를 예로 봅시다!



그리고 2번 카메라는 처음에 화살표 2개 (상(0), 우(1))를 가지고 있습니다.


2번 카메라를 270도 회전하기 위해서는 90도를 3번 회전해야 합니다!

그렇다면 2번 카메라가 가르키는 방향은 (좌(3), ?(4)) 가 되겠죠!

4번 돌았다는 것은 결국 360도 한바퀴를 돌았다는 의미이므로 (좌(3), 상(0)) 이 됩니다.


위의 정보들을 배열로 만들어 놓으면 굉장히 편리해지겠죠!


배열로만 만들어 놓으면 for문을 통해서 어떤 카메라든 쉽게 돌릴 수 있습니다!!


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int csize[6= {0,4,2,44,1};
int camera[6][4= {{}, {0}, {1,3}, {01}, {0,1,3}, {0,1,2,3}};
int dcnt[6= {0,1,2,2,3,4};

for(int rot = 0; rot < csize[ca]; rot++){            
            for(int d= 0; d < dcnt[ca]; d++){
                int p[2= {r,c};
                int dir = (rot+camera[ca][d])%4;
                
                //감시영역 체크 코드
                //...
                //
            }
            for(int d = 0; d < dcnt[ca]; d++){
                int p[2= {r,c};
                int dir = (rot+camera[ca][d])%4;
                //감시영역 제거 코드
                //...
                //
            }
        }
cs


csize가 바로 90도로 돌릴때, 서로 다른 방향을 보는 카메라의 수 입니다.

camera[6][4]는 카메라가 바라보는 방향의 종류입니다.

그리고 dnct가 카메라가 바라보는 방향의 개수 입니다.


이렇게 미리 정보들을 배열로 만들면, 어떤 카메라를 돌릴 때, 번호에 따라서 for문을 2개만 이용하면 카메라를 돌릴 수 있는 것 입니다!

if문과  switch 문으로 중복 코드가 너무 많이 생산된다고 생각한다면, 위처럼 테이블을 만들어서 관리해 봅시다!

생각보다 실수하는 것도 줄어들고 프로그래밍 속도도 굉장히 빨라진답니다!!


두 번째, 카메라를 비추는 영역을 어떻게 처리할지.


주어지는 맵의 정보를 보면, 바닥은 0, 카메라는 1~5, 벽은 6 입니다.

프로그래밍을 할 때 자연스럽게 '그럼, 카메라에 의해 감시되는 부분은 -1로 하지 뭐~' 라고 생각하실 수 있습니다.

그러면 다음과 같은 경우는 어떻게 처리할까요!?




(0,0)과 (0,2)에 1번 카메라가 오른쪽 방향을 보게 설치했다고 가정하겠습니다.




(0,0) 카메라의 오른쪽 부분을 감시합니다!

(0,2) 카메라의 오른쪽도 감시한다고 체크합니다.


이제, (0,2)의 카메라를 90도 회전해서 아래 방향을 감시한다고 만들겠습니다!

그렇다면, (0,2)이 현재 감시하는 방향들의 바닥은 원래대로 돌려야겠죠!

만약, 이 때 감시되는 영역을 -1로만 했다면 다음과 같은 상황이 벌어질 겁니다.




이렇게, (0,2)의 카메라들이 바라보는 방향의 바닥은 다시 정상이 되버리는 것이죠! (0,0)의 카메라가 감시를 하고있는데도 말이죠!

생각보다 이를 처리하기 위한 방법은 쉽습니다.

'바닥이 감시되는 상태를 0 미만으로 하고, 감시되는 영역은 계속 -1을 하는 것' 입니다.


이 방법을 적용해서 다시 살펴봅시다.




오른쪽 감시할 때, (0,0)이 바라보는 방향의 바닥을 모두 -1 합니다.



다음 (0,2) 카메라 오른쪽 부분을 또 -1 합니다.



이제 (0,2) 카메라의 감시를 해제하려면 반대로 (0,2)오른쪽 부분에 +1을 하면 됩니다!



(0,2) 카메라가 아래를 감시하면 다음과 같이 변하는 것이죠!

코드로 확인해 봅시다.


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
if(map[r][c] > 0 && map[r][c] != 6){
        int ca = map[r][c];
 
        for(int rot = 0; rot < csize[ca]; rot++){
            
            for(int d= 0; d < dcnt[ca]; d++){
                int p[2= {r,c};
                int dir = (rot+camera[ca][d])%4;
                
                while(p[0< n && p[1]< m && p[0>= 0 && p[1>= 0){
                    if(map[p[0]][p[1]] == 6break;
 
                    if(map[p[0]][p[1]] <= 0){
                        map[p[0]][p[1]]--;
                    }
                    p[0]+= dr[dir];
                    p[1]+= dc[dir];
                }
            }
            
            
 
            for(int d = 0; d < dcnt[ca]; d++){
                int p[2= {r,c};
                int dir =  (rot+camera[ca][d])%4;
                
                while(p[0>= 0 && p[1>= 0 && p[0< n && p[1< m){
                    if(map[p[0]][p[1]] == 6break;
                    if(map[p[0]][p[1]] < 0 ){
                        map[p[0]][p[1]]++;
                    }
                    p[0]+= dr[dir];
                    p[1+= dc[dir];
                }
            }
        }
    }
cs


아까 돌리는 코드와 합치면 다음과 같은 모습이 됩니다!

카메라는 벽 뒤를 감시할 수 없으므로, 벽이 나오면 break를 해줍니다.


이제, 나머지는 2차원 구간을 dfs로 탐색하면서 카메라의 회전을 처리하면 됩니다!

2차원 구간을 재귀로 탐색하는 방법은 여기에서 확인해 주세요!


코드


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
#include<iostream>
 
using namespace std;
 
int dr[4= {-1,0,1,0};
int dc[4= {010,-1};
 
int csize[6= {0,4,2,44,1};
int camera[6][4= {{}, {0}, {1,3}, {01}, {0,1,3}, {0,1,2,3}};
int dcnt[6= {0,1,2,2,3,4};
 
int map[8][8], n, m;
int MIN(int i1, int i2){return i1 < i2 ? i1 : i2;}
int getNum(){
    int res = 0;
    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < m; j++){
            res += map[i][j] == 0;
        }
    }
    return res;
}
 
int dfs(int r, int c){
    if(r == n){
        return getNum();
    }
 
    int next[2= {r, c+1};
    if(next[1== m){
        next[0++;
        next[1= 0;
    }
    int res = 0x3f3f3f3f;
 
    if(map[r][c] > 0 && map[r][c] != 6){
        int ca = map[r][c];
 
        for(int rot = 0; rot < csize[ca]; rot++){
            
            for(int d= 0; d < dcnt[ca]; d++){
                int p[2= {r,c};
                int dir = (rot+camera[ca][d])%4;
                
                while(p[0< n && p[1]< m && p[0>= 0 && p[1>= 0){
                    if(map[p[0]][p[1]] == 6break;
 
                    if(map[p[0]][p[1]] <= 0){
                        map[p[0]][p[1]]--;
                    }
                    p[0]+= dr[dir];
                    p[1]+= dc[dir];
                }
            }
            
            res = MIN(res, dfs(next[0],next[1]));
 
            for(int d = 0; d < dcnt[ca]; d++){
                int p[2= {r,c};
                int dir =  (rot+camera[ca][d])%4;
                
                while(p[0>= 0 && p[1>= 0 && p[0< n && p[1< m){
                    if(map[p[0]][p[1]] == 6break;
                    if(map[p[0]][p[1]] < 0 ){
                        map[p[0]][p[1]]++;
                    }
                    p[0]+= dr[dir];
                    p[1+= dc[dir];
                }
            }
        }
    } 
    else{
        res = dfs(next[0], next[1]);
    }
 
    return res;
}
 
int main(){
    cin >> n >> m;
    for(int i = 0 ; i < n; i++){
        forint j = 0; j < m; j++){
            cin >> map[i][j];
        }
    }
    cout << dfs(0,0);
 
    return 0;
}
cs


시간복잡도


CCTV의 최대 개수는 8개 입니다.


CCTV 하나당 최대 회전 수는 4개 이고, 카메라당 최대 감지 범위가 2*n-2개 이기 때문에, 

시간 복잡도는 입니다.


반응형