★★★★★다시 풀어볼 문제★★★★★
알고리즘 문제해결전략 1권
6.5 문제: 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)
완전탐색 문제
첫번째 코드는 시간상 오류가 나는 코드이다.
내가 보기에 슈퍼컴퓨터라면 정답은 나올 것 같다;;
나름 중복되는 경우의 수를 지우기 위해 재귀함수의 for문을 건드렸지만, 아주 미세한 차이만을 나타냈을 뿐이었다.
일단 나름 책에서의 첫문제를 적용해서 풀려고 노력은 했다는 점은 만족한다.
정답 코드는 일단 for문에서 경우의 수를 줄이려고 한 것이 아니라는 점이 좋았다.
나 같은 경우에는 항상 for문을 복잡하게 만들어서 경우의 수를 줄이려고 하는 습관이 있었는데 그것을 깰 수 있었다.
내가 실수한 점은 진짜 무식하게 모든 경우를 돌려서 블록을 맞추려고 했던 점이고,
정답 코드는 왼쪽 상단부터 블록을 맞춰가면서 푼다는 점이었다.
그렇기 때문에 항상 왼쪽과 위의 칸은 맞춰져 있다는 가정 <- 이 가정도 굉장히 중요했다. 이 때문에 내가 첫번째 실수했던 코드에서
블록을 채우는 배열함수를 바꿔야 한다는 것을 깨달았다.
그래서 오히려 경우의 수를 대폭 줄일 수 있었다. (기존의 내 코드에 비해서)
또한 블록이 3칸짜리를 채우는 것이기 때문에 빈칸이 3의 배수로 존재해야 한다는 점.
간과하기 쉽지만 간과해서는 안되는 점이었다.
난이도 '하' 라고 주어졌지만 은근히 생각할 게 많은 문제인 것 같다...
나름 N-Queen 같은 문제는 쉽게 풀었는데... 알고리즘은 성향에 따라 본인이 느끼는 수준이 천차만별인 것 같다.. 특히 나같은 초보일 수록..
실수 코드
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 | #include<iostream> using namespace std; int H, W; char map[21][21]; int dx[4][2] = { { -1,0},{-1,0},{1,0},{1,0} }; int dy[4][2] = { { 0,1},{0,-1},{0,1},{0,-1} }; int ans; bool isCovered[21][21]; void print() { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cout << isCovered[i][j] << " "; } cout << endl; } cout << "-------------------------------" << endl; } void cover(int x, int y) { bool finished = true; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (!isCovered[i][j]) { finished = false; break; } } if (!finished) { break; } } if (finished) { ans += 1; return; } for (int i = x; i < H; i++) { if (x != i) { for (int j = 0; j < W; j++) { if (map[i][j] == '.' && !isCovered[i][j]) { for (int d = 0; d < 4; d++) { int x0 = i + dx[d][0]; int y0 = j + dy[d][0]; int x1 = i + dx[d][1]; int y1 = j + dy[d][1]; if (map[x0][y0] == '.' && map[x1][y1] == '.' && x0 >= 0 && y0 >= 0 && x0 < H && y0 < W && x1 >= 0 && y1 >= 0 && x1 < H && y1 < W && !isCovered[x0][y0] && !isCovered[x1][y1]) { isCovered[i][j] = true; isCovered[x0][y0] = true; isCovered[x1][y1] = true; print(); cover(i, j); isCovered[i][j] = false; isCovered[x0][y0] = false; isCovered[x1][y1] = false; print(); } } } } } else { for (int j = y; j < W; j++) { if (map[i][j] == '.' && !isCovered[i][j]) { for (int d = 0; d < 4; d++) { int x0 = i + dx[d][0]; int y0 = j + dy[d][0]; int x1 = i + dx[d][1]; int y1 = j + dy[d][1]; if (map[x0][y0] == '.' && map[x1][y1] == '.' && x0 >= 0 && y0 >= 0 && x0 < H && y0 < W && x1 >= 0 && y1 >= 0 && x1 < H && y1 < W && !isCovered[x0][y0] && !isCovered[x1][y1]) { isCovered[i][j] = true; isCovered[x0][y0] = true; isCovered[x1][y1] = true; print(); cover(i, j); isCovered[i][j] = false; isCovered[x0][y0] = false; isCovered[x1][y1] = false; print(); } } } } } } return; } int main() { freopen("input.txt", "r", stdin); int tc; cin >> tc; for (int t = 1; t <= tc; t++) { //맵 초기화 for (int i = 0; i < 21; i++) { for (int j = 0; j < 21; j++) { map[i][j] = '#'; isCovered[i][j] = false; } } ans = 0; cin >> H >> W; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cin >> map[i][j]; if (map[i][j] == '#') { isCovered[i][j] = true; } } } cover(0, 0); cout << ans << endl; } return 0; } | cs |
정답 코드
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 | #include<iostream> using namespace std; int H, W; char map[21][21]; int dx[4][2] = { { 1,1},{1,1},{1,0},{1,0} }; int dy[4][2] = { { 0,-1},{0,1},{1,1},{0,1} }; int ans; int n_num; int n; bool isCovered[21][21]; void print() //진행과정 디버깅 용 { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cout << isCovered[i][j] << " "; } cout << endl; } cout << "-------------------------------" << endl; } void cover() { bool finished = true; int x = -1; int y = -1; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (map[i][j]=='.' && !isCovered[i][j]) { x = i; y = j; finished = false; break; } } if (!finished) { break; } } if (finished) { ans += 1; return; } for (int d = 0; d < 4; d++) { int x0 = x + dx[d][0]; int y0 = y + dy[d][0]; int x1 = x + dx[d][1]; int y1 = y + dy[d][1]; if (map[x0][y0] == '.' && map[x1][y1] == '.' && x0 >= 0 && y0 >= 0 && x0 < H && y0 < W && x1 >= 0 && y1 >= 0 && x1 < H && y1 < W && !isCovered[x0][y0] && !isCovered[x1][y1]) { isCovered[x][y] = true; isCovered[x0][y0] = true; isCovered[x1][y1] = true; //print(); cover(); isCovered[x][y] = false; isCovered[x0][y0] = false; isCovered[x1][y1] = false; //print(); } } return; } int main() { //freopen("input.txt", "r", stdin); int tc; cin >> tc; for (int t = 1; t <= tc; t++) { //맵 초기화 for (int i = 0; i < 21; i++) { for (int j = 0; j < 21; j++) { map[i][j] = '#'; isCovered[i][j] = false; } } ans = 0; n_num = 0; cin >> H >> W; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cin >> map[i][j]; if (map[i][j] == '#') { isCovered[i][j] = true; } else if (map[i][j] = '.') { n_num += 1; } } } if (n_num % 3 == 0) { cover(); } else { ans = 0; } cout << ans << endl; } return 0; } | cs |
반응형
'알고리즘 > Algospot' 카테고리의 다른 글
| PICNIC (C언어) (0) | 2018.06.25 |
|---|---|
| 28.2 문제: 고대어 사전(문제 ID: DICTIONARY) (0) | 2017.12.07 |
| 외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하) (0) | 2017.11.13 |
| 6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중) (0) | 2017.11.09 |
| 6.3 문제 : 소풍 ( 문제 ID: PICNIC , 난이도: 하) (0) | 2017.11.09 |