Search
Duplicate

매직 스타

주차
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++
복사