티스토리 뷰
브루트 포스
- CCTV의 좌표를 미리 저장해둔다. 그리고 완전 탐색 ㄱㄱ링
- 코드를 수정하다가 연산자 하나 안 고쳐서 계속 틀렸다...실전에서도 이러면 꽤 곤란하다,,...,;;
- 상하좌우 각각 확인하는 함수를 미리 만들어 놓으면 편하다. 계속 써야 하기 때문,,
소스 코드
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 | #include <iostream> #include <algorithm> #define FOR(i,a,b) for(int i = a; i < b; i++) #define pii pair<int, int> using namespace std; int N, M, ans = 100000; int idx; int map[9][9]; pii cctv[9]; int check() { int cnt = 0; FOR(i, 0, N) FOR(j, 0, M) if (map[i][j] == 0) cnt++; return cnt; } void UP(int x, int y) { int k = x; while (k >= 0 && map[k][y] != 6) { if (map[k][y] == 0) map[k][y] = 7; k--; } } void DOWN(int x, int y) { int k = x; while (k < N && map[k][y] != 6) { if (map[k][y] == 0) map[k][y] = 7; k++; } } void LEFT(int x, int y) { int k = y; while (k >= 0 && map[x][k] != 6) { if (map[x][k] == 0) map[x][k] = 7; k--; } } void RIGHT(int x, int y) { int k = y; while (k < M && map[x][k] != 6) { if (map[x][k] == 0) map[x][k] = 7; k++; } } void dfs(int depth) { if (depth == idx) { ans = min(ans, check()); return; } int de[9][9] = { 0, }; FOR(i, 0, N) FOR(j, 0, M) de[i][j] = map[i][j]; int x = cctv[depth].first; int y = cctv[depth].second; int u, v, w, k; switch (map[x][y]) { case 1: //상 UP(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //하 DOWN(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //좌 LEFT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //우 RIGHT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; break; case 2: //상하 UP(x, y); DOWN(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //좌우 LEFT(x, y); RIGHT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; break; case 3: //상좌 UP(x, y); LEFT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //상우 UP(x, y); RIGHT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //하좌 DOWN(x, y); LEFT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //하우 DOWN(x, y); RIGHT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; break; case 4: //상하좌 UP(x, y); DOWN(x, y); LEFT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //상하우 UP(x, y); DOWN(x, y); RIGHT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //하좌우 DOWN(x, y); LEFT(x, y); RIGHT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; //상좌우 UP(x, y); LEFT(x, y); RIGHT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; break; case 5: //상하좌우 UP(x, y); DOWN(x, y); LEFT(x, y); RIGHT(x, y); dfs(depth + 1); FOR(i, 0, N) FOR(j, 0, M) map[i][j] = de[i][j]; break; } } int main() { cin >> N >> M; FOR(i, 0, N) FOR(j, 0, M) { cin >> map[i][j]; if (map[i][j] != 0 && map[i][j] != 6) { cctv[idx].first = i; cctv[idx++].second = j; } } dfs(0); cout << ans; } | cs |
반응형
'백준 온라인 저지' 카테고리의 다른 글
200122 BOJ 2819 상근이의 로봇 (0) | 2020.01.23 |
---|---|
190704 BOJ 1309 동물원 (0) | 2019.07.04 |
190408 BOJ 14891번 톱니바퀴 (0) | 2019.04.08 |
190407 BOJ 12100번 2048 (Easy) (0) | 2019.04.07 |
190326 BOJ 3190번 뱀 (0) | 2019.03.26 |
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 프로그래밍 온라인 강의
- 개발자 취업
- 컴퓨터공학
- 패스트캠퍼스
- Fast Campus
- #패스트캠퍼스 #프로그래밍대학생서포터즈 #올인원패키지 #컴퓨터공학 #성공하는프로그래밍공부법
- 코딩 면접
- 올인원 패키지
- c언어
- 운영체제
- 자료구조
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함