티스토리 뷰
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
|
import java.io.*;
import java.util.*;
public class boj_15683 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1}; // 남동북서
static int[][] map1 = new int[10][10];
static int[][] map2 = new int[10][10];
static List<int[]> cctv = new ArrayList<>();
static int row, col, min;
public static void main(String[] args) throws IOException {
input();
solve();
}
static void input() throws IOException {
st = new StringTokenizer(br.readLine());
row = Integer.parseInt(st.nextToken());
col = Integer.parseInt(st.nextToken());
for (int i = 0; i < row; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
map1[i][j] = Integer.parseInt(st.nextToken());
if (map1[i][j] == 0) min++;
if (map1[i][j] > 0 && map1[i][j] < 6) {
cctv.add(new int[]{i, j});
}
}
}
}
static void solve() {
for (int temp = 0; temp < (1 << (2 * cctv.size())); temp++) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
map2[i][j] = map1[i][j];
}
}
int brute = temp;
for (int[] now : cctv) {
int dir = brute % 4;
brute /= 4;
int x = now[0];
int y = now[1];
switch (map1[x][y]) {
case 1:
upd(x, y, dir);
break;
case 2:
upd(x, y, dir);
upd(x, y, dir + 2);
break;
case 3:
upd(x, y, dir);
upd(x, y, dir + 1);
break;
case 4:
upd(x, y, dir);
upd(x, y, dir + 1);
upd(x, y, dir + 2);
break;
default:
upd(x, y, dir);
upd(x, y, dir + 1);
upd(x, y, dir + 2);
upd(x, y, dir + 3);
}
}
int val = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (map2[i][j] == 0) val++;
}
}
min = Math.min(min, val);
}
System.out.println(min);
}
static boolean OOB(int x, int y) { // Out of Bounds
return x < 0 || x >= row || y < 0 || y >= col;
}
static void upd(int x, int y, int dir) {
dir %= 4;
while (true) {
x += dx[dir];
y += dy[dir];
if (OOB(x, y) || map2[x][y] == 6) return; // 범위 벗어나거나 벽 만나면
if (map2[x][y] != 0) continue; // 빈칸이 아닐경우
map2[x][y] = 7; // 7로 마킹
}
}
}
|
cs |
- 시뮬레이션
- 어렵다 ,,
- 1. cctv 최대 개숫가 8개니까 4^8 경우의 수로 전부 돌려서 그 중에 최솟값을 찾는법
- 2. cctv 1-2-3-4-5 순서로 돌리는 방법
- 근데 다시 생각해보니까 2번은 말이 안된다. 맵을 돌면서 cctv를 발견하면 그때마다 가장 적합한 해를 찾는 방법으로 해도 맞지않고
결국엔 전부 동시에 cctv를 돌려야하고 가능한 방향수는 최대 4^8 -1 이니까 이걸 전부 돌려봐야한다.
1. 입력받을때 0의 수 체크, cctv는 list에 넣어준다.
2. 총 0 ~ 4^ cctv갯수 번 roof를 돈다. (temp)
3. 방향 조합의 수를 4진수라고 생각 (최대 4방향이니 0, 1, 2, 3 )
10진수의 수에서 각 자리 뽑는것처럼 4진수도 똑같은 방법으로 뽑을 수 있음
4. upd() 는 매개변수로 들어온 방향으로 쭉 방문했다는 마킹을 남긴다. (벽, 범위 주의)
5. 1번 cctv는 단방향이니 upd(x, y, dir) 이런식인데 2,3,4 번의 경우 따로 처리해주어야 한다.
6. (temp) 루프에서 매번 map2에 마킹된것을 보고 0을 카운팅하고 최솟값을 계속 갱신해준다.
'PS > boj' 카테고리의 다른 글
boj)10972 - 다음 순열 (0) | 2020.11.30 |
---|---|
boj)18808 - 스티커 붙이기 (0) | 2020.11.27 |
boj)1182 - 부분수열의 합 (0) | 2020.11.23 |
boj)9663 - N-Queen (0) | 2020.11.19 |
boj)15666 - N과 M (12) (0) | 2020.11.19 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 이펙티브자바 아이템59
- 백기선 스터디
- HTTP 완벽 가이드
- 이펙티브자바 아이템60
- 드림코딩
- 패스트캠퍼스 컴퓨터공학 완주반
- 이펙티브자바 스터디
- HTTP 완벽가이드
- REST API
- BOJ
- JS 딥다이브
- Spring Security
- GCP
- 모던자바스크립트
- js api
- 킹수빈닷컴
- JPA 연관관계 매핑
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 이펙티브자바
- js array
- 백준
- 프로그래머스
- dreamcoding
- 프로그래머스 SQL
- http
- 김영한 http
- java
- js promise
- 김영한 JPA
- ㅇㄷㅇㅈ
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함