C언어로 백준 15683: 감시

by 코딩하는 낙타 2020. 3. 17. 14:17

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

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할

www.acmicpc.net

내 풀이:

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

#include <stdio.h>
 
int N, M, ans = 64, num_camera = 0, cctv[64][3], dy[4] = { -1, 0, 1, 0 }, dx[4] = { 0, 1, 0, -1 };
 
void see(int new[][8], int y, int x, int dir) {
    int ny, nx;
    ny = y + dy[dir];
    nx = x + dx[dir];
 
    while (0 <= ny && ny <= N - 1 && 0 <= nx && nx <= M - 1 && new[ny][nx] != 6) {
        if (new[ny][nx] == 0) {
            new[ny][nx] = 9;
        }
        ny += dy[dir];
        nx += dx[dir];
    }
}
 
int go(int idx, int now[][8]) {
    if (idx == num_camera) {
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (now[i][j] == 0) {
                    res += 1;
                }
            }
        }
        if (ans > res)
            ans = res;
        return 0;
    }
    
    int y, x, k;
    y = cctv[idx][0];
    x = cctv[idx][1];
    k = cctv[idx][2];
 
    if (k == 1) {
        for (int dir = 0; dir < 4; dir++) {
            int new[8][8] = { 0 };
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    new[i][j] = now[i][j];
                }
            }
            
            see(new, y, x, dir);
            go(idx + 1, new);
        }
    }
 
    else if (k == 2) {
        for (int dir = 0; dir < 2; dir++) {
            int new[8][8] = { 0 };
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    new[i][j] = now[i][j];
                }
            }
 
            see(new, y, x, dir);
            see(new, y, x, dir + 2);
            go(idx + 1, new);
        }
    }
 
    else if (k == 3) {
        for (int dir = 0; dir < 4; dir++) {
            int new[8][8] = { 0 };
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    new[i][j] = now[i][j];
                }
            }
 
            see(new, y, x, dir);
            see(new, y, x, (dir + 1) % 4);
            go(idx + 1, new);
        }
    }
 
    else if (k == 4) {
        for (int dir = 0; dir < 4; dir++) {
            int new[8][8] = { 0 };
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    new[i][j] = now[i][j];
                }
            }
 
            see(new, y, x, dir);
            see(new, y, x, (dir + 1) % 4);
            see(new, y, x, (dir + 2) % 4);
            go(idx + 1, new);
        }
    }
 
    else if (k == 5) {
        
        int new[8][8] = { 0 };
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                new[i][j] = now[i][j];
            }
        }
 
        see(new, y, x, 0);
        see(new, y, x, 1);
        see(new, y, x, 2);
        see(new, y, x, 3);
        go(idx + 1, new);
        
    }
 
    return 0;
}
 
int main(void) {
    int arr[8][8];
 
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] != 0 && arr[i][j] != 6) {
                cctv[num_camera][0] = i;
                cctv[num_camera][1] = j;
                cctv[num_camera][2] = arr[i][j];
                num_camera += 1;
            }
        }
    }
 
    go(0, arr);
    printf("%d", ans);
    return 0;
}

 

시간: 8ms

2차원 배열을 함수로 보내주는 방법을 알지 못해 나름 고생을 한 문제이다. new에 now를 딥카피하여 이용하기 위해 2중 for문을 이용해주었다.

저작자표시

'C언어 > 문제풀이 (삼성 A형 대비)' 카테고리의 다른 글

C언어로 풀어보는 백준 17281번: ⚾ (0)	2020.03.21
C언어로 백준 16236번: 아기 상어 (삼성 A형 기출 문제) (0)	2020.03.17
C언어로 풀어보는 백준 17144번: 미세먼지 안녕! (0)	2020.03.10