카테고리 없음
백준 15683 - 감시
jin_j_i_n
2021. 4. 15. 12:47
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
중복 순열 + 시뮬레이션
중복 순열은 재귀로 구했다
switch문을 쓸땐 break문을 잘 써주자..
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 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 | import java.io.*; import java.util.ArrayList; public class B15683 { // 방향만 다르면되기 때문에 1,2,3,4 방향중 하나면 됨 // 감시카메라가 6개면 4^6 경우의 수 static int[] list; static ArrayList<Point> cctvs; static int[][] origin; static int N; static int M; static int cctvCnt = 0; static int min = 70; public static class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } } public static void bruteForce(int idx) { if (idx == cctvCnt) { // 사각지대 개수 구함 int[][] tmp = new int[N][M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { tmp[i][j] = origin[i][j]; } } min = Math.min(min, getBlindSpot(tmp)); return; } else { for (int i = 1; i <= 4; i++) { list[idx] = i; bruteForce(idx + 1); } } } public static int getBlindSpot(int[][] arr) { int cnt = 0; for (int i = 0; i < cctvs.size(); i++) { Point tmp = cctvs.get(i); int x = tmp.x; int y = tmp.y; int cctv = origin[x][y]; int direction = list[i]; // System.out.println("cctv : " + cctv + " , direct : " + direction); switch (cctv) { case 1: monitoring(x, y, direction, arr); break; case 2: switch (direction) { case 1: case 3: monitoring(x, y, 1, arr); monitoring(x, y, 3, arr); break; case 2: case 4: monitoring(x, y, 2, arr); monitoring(x, y, 4, arr); break; } break; case 3: switch (direction) { case 1: monitoring(x, y, 1, arr); monitoring(x, y, 4, arr); break; case 2: monitoring(x, y, 1, arr); monitoring(x, y, 2, arr); break; case 3: monitoring(x, y, 2, arr); monitoring(x, y, 3, arr); break; case 4: monitoring(x, y, 3, arr); monitoring(x, y, 4, arr); break; } break; case 4: switch (direction) { case 1: monitoring(x, y, 1, arr); monitoring(x, y, 2, arr); monitoring(x, y, 4, arr); break; case 2: monitoring(x, y, 1, arr); monitoring(x, y, 2, arr); monitoring(x, y, 3, arr); break; case 3: monitoring(x, y, 2, arr); monitoring(x, y, 3, arr); monitoring(x, y, 4, arr); break; case 4: monitoring(x, y, 1, arr); monitoring(x, y, 3, arr); monitoring(x, y, 4, arr); break; } break; case 5: monitoring(x, y, 1, arr); monitoring(x, y, 2, arr); monitoring(x, y, 3, arr); monitoring(x, y, 4, arr); break; default: break; } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (arr[i][j] == 0) cnt++; } } return cnt; } public static void monitoring(int x, int y, int dir, int[][] room) { int val = -1; switch (dir) { case 1: // 북쪽 for (int i = x - 1; i >= 0; i--) { if (room[i][y] == 6) return; else room[i][y] = val; } break; case 2:// 서쪽 for (int j = y - 1; j >= 0; j--) { if (room[x][j] == 6) return; else room[x][j] = val; } break; case 3:// 남쪽 for (int i = x + 1; i < N; i++) { if (room[i][y] == 6) return; else room[i][y] = val; } break; case 4:// 동쪽 for (int j = y + 1; j < M; j++) { if (room[x][j] == 6) return; else room[x][j] = val; } break; } return; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] inputs = br.readLine().split(" "); N = Integer.parseInt(inputs[0]); M = Integer.parseInt(inputs[1]); origin = new int[N][M]; cctvs = new ArrayList<>(); for (int i = 0; i < N; i++) { inputs = br.readLine().split(" "); for (int j = 0; j < M; j++) { int tmp = Integer.parseInt(inputs[j]); if (tmp != 0 && tmp != 6) { cctvs.add(new Point(i, j)); cctvCnt++; } origin[i][j] = tmp; } } list = new int[cctvCnt]; bruteForce(0); System.out.println(min); } } | cs |