Search
moon
sun

매직 스타

주차
0
문제번호
3967
언어
C++
티어
골드
유형
백트래킹
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

Memo

구현 방법

•
합이 26 임을 확인하는 부분을 만듭니다.
•
x와 A~L의 좌표를 저장하여 백트래킹을 돌립니다.

개인적인 생각

•
아이디어적인 측면에서, 백트래킹을 어떤 방법으로 돌릴지에 대한 부분이 어렵게 느껴졌습니다.
•
체크 포인트(좌표)가 많아 실수를 하면 찾기 어렵습니다.
•
백트레킹이 결코 쉬운 문제가 아님을 깨닫게 해주는 문제였습니다.

Code

제출 날짜

@4/1/2021

메모리

2020 KB

시간

0 ms
#include <iostream> #include <vector> #define endl "\n" int g_map[6][10]; bool alphabet_table[13]; int coord_set[6][4][2] = {{{0, 4}, {1, 3}, {2, 2}, {3, 1}}, {{3, 1}, {3, 3}, {3, 5}, {3, 7}}, {{3, 7}, {2, 6}, {1, 5}, {0, 4}}, {{1, 1}, {2, 2}, {3, 3}, {4, 4}}, {{4, 4}, {3, 5}, {2, 6}, {1, 7}}, {{1, 7}, {1, 5}, {1, 3}, {1, 1}}}; std::vector<std::pair<int, int> >coord; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::string tmp; for (int i = 0; i < 5 ; i++) { std::cin >> tmp; for (int j = 0 ; j < tmp.size(); j++) { if (tmp[j] == '.') { g_map[i][j] = 20; continue; } if ('A' <= tmp[j] && tmp[j] <= 'L') { g_map[i][j] = tmp[j] - 'A' + 1; alphabet_table[g_map[i][j]] = 1; } else g_map[i][j] = 0; coord.push_back({i, j}); } } } bool is_lastpart(int y, int x) { return ((y == 1 && x == 7) || (y == 3 && x == 1) || (y == 3 && x == 7) || (y == 4 && x == 4)); } bool sum(int ind) { int cnt = 0; for (int i = 0 ; i < 4 ; i++) cnt += g_map[coord_set[ind][i][0]][coord_set[ind][i][1]]; if (cnt == 26) return (1); return (0); } bool check(int y, int x) { if (y == 1 && x == 7) { if (!sum(5)) // if not 26 return (0); } else if (y == 3 && x == 1) { if (!sum(0)) return (0); } else if (y == 3 && x == 7) { if (!sum(1) || !sum(2)) return (0); } else if (y == 4 && x == 4) { if (!sum(3) || !sum(4)) return (0); } return (1); } bool backtracking(int ind) { if (ind == coord.size()) return (1); int y = coord[ind].first; int x = coord[ind].second; if (g_map[y][x]) { if (is_lastpart(y, x) && !check(y, x)) return (false); if(backtracking(ind + 1)) return (true); else return (false); } for (int i = 1 ; i <= 12 ; i++) { if (!alphabet_table[i]) { g_map[y][x] = i; if (is_lastpart(y, x) && !check(y, x)) { g_map[y][x] = 0; continue; } //after checking alphabet_table[i] = 1; if (backtracking(ind + 1)) return (true); alphabet_table[i] = 0; g_map[y][x] = 0; } } return (false); } void solve() { backtracking(0); } void print_val() { char tmp; for (int i = 0 ; i < 5 ; i++) { for (int j = 0; j < 9 ; j++) { if (g_map[i][j] == 20) std::cout << '.'; else { tmp = (char)g_map[i][j] + 'A' - 1; std::cout << tmp; } } std::cout << endl; } } int main() { input(); solve(); print_val(); return (0); }
C++
복사