스도쿠 ( 백트레킹 문제를 더 고민해보자!!, 이전에 백트레킹인줄 몰라서 틀린게 좀 있는거 같다. 카카오 원판 순회?)
음 완전탐색해야 될거 같다. 가능한 놈들을 추려서 결국에 가능한 한가지 경우만 도출하면 될거같은데 구현 방법이 떠오르지 않는다.
후보를 어떻게 저장해야 될까, 각 칸마다 저장하는건 올바르지 못한거 같다. 각 행,열 마다 후보들을 저장해놓자.
그리고 3x3 그리드 마다 가능한 후보들을 저장해 놓자. 그리고 각 칸마다 가능한 놈들을 행,열,그리드에서 공통인 것을 찾으면 될거 같다.
일단 테스트 케이스는 맞았는데 처음에는 틀렸었다.
틀린 이유는 행,열,그리드 모두를 만족하는 숫자를 넣어줘야 하는데 그걸 구현을 잘못했었다. 다시 한 방법은
bool num_r[10] = { 0 };
bool num_c[10] = { 0 };
bool num_g[10] = { 0 };
if ((num_r[i] & num_c[i] & num_g[i]) == 1 )
이렇게 세개다 각각 확인했는데 좀 비효율적인거 같다. 다른 구현 방법이 떠오르지 않는데 나중에 다시 풀이를 꼭 찾아보는게 좋겠다. 질문 검색 보다보니 어떤분 코드는 내 코드의 절반이더라.....
일단 반례 하나 찾았는데 모두 0인 경우...
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
내 코드
1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 -1 -1 -1
7 8 9 -1 -1 -1 1 2 3
2 1 4 3 6 5 8 7 -1
3 6 5 2 1 4 9 -1 -1
8 7 -1 9 -1 -1 2 1 4
5 3 1 6 4 2 -1 9 7
6 4 2 5 3 1 -1 -1 8
9 -1 7 8 -1 -1 3 4 1왜 틀렸는지 알겠다. 백트래킹으로 쭉 들어가서 확인해야 한다. 내 방법은 앞뒤로 독립적이라서 2행에서 456123까지 해하고 이상있으면 다른걸 해야되는데 다른걸 안한다......
진정한 완전탐색일려면 이 모든걸 결정하고 확인했어야 하는데 나는 r,c 한 곳에 대해서만 확인하는 방법이다....
어려운 문제였다......
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>
using namespace std;
#define NUM 101
#define MAXV 10001
int arr[10][10];
vector<int>row_cands[10];
vector<int>col_cands[10];
vector<int>grid_cands[10][10];
struct dir {
int r, c;
};
void addCandStride(dir d, int ind) {
bool nums[10] = { 0 };
int r, c;
if (d.r == 1) {
r = 0;
c = ind;
}
else if (d.c == 1) {
c = 0;
r = ind;
}
for (int i = 0; i < 9; i++) {
r = r + d.r;
c = c + d.c;
nums[arr[r][c]] = 1;
}
for (int i = 1; i < 10; i++) {
if (nums[i] == 0)
{
if (d.r == 1) {
col_cands[ind].push_back(i);
}
else if (d.c == 1) {
row_cands[ind].push_back(i);
}
}
}
}
void addCandGrid() {
int st_r, st_c;
bool nums[10] = { 0 };
for(int st_r =0; st_r < 9 ; st_r+=3){
for (int st_c = 0; st_c < 9; st_c += 3) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
nums[arr[st_r + i][st_c + j]] = 1;
}
}
for (int i = 1; i < 10; i++) {
if (nums[i] == 0)
grid_cands[st_r][st_c].push_back(i);
}
memset(nums, 0, sizeof(nums));
}
}
}
int getCommon(int r, int c) {
bool num_r[10] = { 0 };
bool num_c[10] = { 0 };
bool num_g[10] = { 0 };
for (int i = 0; i < row_cands[r].size(); i++) {
num_r[row_cands[r][i]] = 1;
}
for (int i = 0; i < col_cands[c].size(); i++) {
num_c[col_cands[c][i]] = 1;
}
int gr = (r / 3) * 3;
int gc = (c / 3) * 3;
for (int i = 0; i < grid_cands[gr][gc].size(); i++) {
num_g[grid_cands[gr][gc][i]] = 1;
}
for (int i = 1; i < 10; i++) {
if ((num_r[i] & num_c[i] & num_g[i]) == 1 ) {
//delete from cands
for (int j = 0; j < row_cands[r].size(); j++) {
if (row_cands[r][j] == i) {
row_cands[r].erase(row_cands[r].begin() + j);
break;
}
}
for (int j = 0; j < col_cands[c].size(); j++) {
if (col_cands[c][j] == i) {
col_cands[c].erase(col_cands[c].begin() + j);
break;
}
}
for (int j = 0; j < grid_cands[gr][gc].size(); j++) {
if (grid_cands[gr][gc][j] == i) {
grid_cands[gr][gc].erase(grid_cands[gr][gc].begin() + j);
break;
}
}
return i;
}
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < 9; i++)
{
addCandStride({ 1,0 }, i);
addCandStride({ 0,1 }, i);
}
addCandGrid();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (arr[i][j] == 0) {
arr[i][j] = getCommon(i, j);
}
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << arr[i][j] << " ";
}
cout << "\n";
}
return 0;
}
다시 고민해봤는데 모든 지점을 채우기 전까지는 성립하는지 확인하는게 어렵지 않나. 완성하고 구분할 단위를 어떻게 분할해야 될지 모르겠다. 이 부분을 해설을 좀 보자.
결국 채워보면서 확인을 해야했다. 백트레킹이라 하는듯 이런 방법을, 매 단계마다 조건이 성립하는지 확인해야 하고, 다음 단계로 넘어갈때 상태를 변경해줘야 한다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>
using namespace std;
#define NUM 101
#define MAXV 10001
int arr[10][10];
bool row[10][10];
bool col[10][10];
//3*3박스로 맞춰야한다.
bool grid[10][10];
int hash3(int r, int c) {
return (r / 3) * 3 + c / 3;
}
void dfs(int depth) {
if (depth == 81) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j ++ ) {
cout << arr[i][j] << " ";
}
cout << "\n";
}
exit(0);
}
int r = depth / 9;
int c = depth % 9;
if (arr[r][c])
dfs(depth + 1);
else {
for (int k = 1; k <= 9; k++) {
if (!col[c][k] && !row[r][k] && !grid[hash3(r, c)][k]) {
arr[r][c] = k;
col[c][k] = 1;
row[r][k] = 1;
grid[hash3(r, c)][k] = 1;
dfs(depth + 1);
arr[r][c] = 0;
col[c][k] = 0;
row[r][k] = 0;
grid[hash3(r, c)][k] = 0;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> arr[i][j];
if (arr[i][j]) {
row[i][arr[i][j]] = 1;
col[j][arr[i][j]] = 1;
grid[hash3(i, j)][arr[i][j]] = 1;
}
}
}
dfs(0);
return 0;
}
비숍
백트래킹 문제다. 비숍을 놓고, 배치 못하는 자리를 어떻게 체크할지가 중요해 보인다.
음 구현 못했는데 , 현재 이동할 수 있는 칸과 불가한 칸을 저장한 배열과 현재 비숍이 이동 불가한 칸을 저장한걸 계속 갱신해야 하는데 함수로 하자니 이차원 배열 반환,넘기기가 copy되서 넘어가는건지 reference로 넘어가는 건지도 잘모르겠었다......
음 내 생각은 재귀함수로 카피해서 넘기는게 돌아올때도 깔금하고 새로 재귀 함수로 들어갈때도 계산만 하면 된다 생각했다. 근데 이 계산만하는데서 틀린거 같은데 그럴바에 그냥 함수 내부에서 하자.
다시 고친대로 구현했는데 시간초과가 발생했다... 뭐 이해는 하는데 어떻게 줄여야 될까...!!
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>
using namespace std;
#define NUM 11
#define MAXV 987654321
int N, M;
int arr[NUM][NUM];
int maxv = 0;
int dir_r[4] = { 1,1,-1,-1 };
int dir_c[4] = { -1,1,-1,1 };
struct rc {
int r, c;
};
int( *getBis(int r, int c) )[NUM]{
int nr, nc;
int bis[NUM][NUM] = { 0 };
for (int i = 0; i < 4; i++) {
nr = r;
nc = c;
bis[nr][nc] = 1;
while (r >= 0 && r < N && c >= 0 && c < N) {
bis[r][c] = 1;
r += dir_r[i];
c += dir_c[i];
}
}
return bis;
}
void dfs(int prev[][NUM], int cur[][NUM],int cnt) {
vector<rc>bishops;
int sum[NUM][NUM];
int (*bis)[NUM];
if (maxv < cnt)
maxv = cnt;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if ( (sum[i][j] = (prev[i][j] | cur[i][j])) == 0) {
bis = getBis(i, j);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum[i][j] |= bis[i][j];
}
}
dfs(sum, bis,cnt+1);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
int cur[NUM][NUM] = { 0 };
dfs(arr,cur,0);
cout << maxv;
return 0;
}다시 고민해 보니까 메모이제이션을 이용하면 시간을 줄일 수 있을것 같다. 비숍위치가 달라도 놓을 수 있는 위치가 동일한 경우들이 있을것 같다. 문제는 이 상태를 어떤 인덱스를 이용해 저장하냐 일듯!?
10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1이게 시간초과 발생하는듯 ㅋㅋ
아무래도 퀸 문제는 경우 제한이 많이되서 시간초과는 안뜨는거 같은데 비숍은 아닌거 같다.....
해설 조금 봤을때는 체스판이 체크 무늬인거 이용하라는데... 모르겠따.......
찾아 봤다....<https://www.acmicpc.net/board/view/34232>
안봤으면 한달은 고민해도 몰랐을 수도...??
여전히 시간 초과가 난다...왜지
근데 여기서 구현이 좀 중요할듯. 두가지가 떠오르는데 두개다 능숙히 할 수 없을거 같다.
첫째는 그냥 n*n배열로 받고 다른건 n/2*n/2 배열로 받는건데 이런 조작에 능숙해야 될거같던데 ㅠ
#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>
using namespace std;
#define NUM 11
#define MAXV 987654321
int N, M;
int arr[NUM][NUM];
int maxv=0,maxv2 = 0;
int dir_r[4] = { 1,1,-1,-1 };
int dir_c[4] = { -1,1,-1,1 };
struct rc {
int r, c;
};
void dfs(int prev[][NUM], int cnt) {
int sum[NUM][NUM];
int bis[NUM][NUM] = { 0 };
if (maxv < cnt)
maxv = cnt;
//i는 행
for (int i = 0; i < N; i+=1) {
int j = i % 2;
//j는 열
for (; j < N; j+=2) {
if (prev[i][j] == 0) {
//i,j위치의 비숍으로 이동을 제한한다.
for (int k = 0; k < 4; k++) {
int nr = i;
int nc = j;
while (nr >= 0 && nr < N && nc >= 0 && nc < N) {
bis[nr][nc] = 1;
nr += dir_r[k];
nc += dir_c[k];
}
}
//sum을 prev랑 bis로 고친다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum[i][j] = prev[i][j] | bis[i][j];
}
}
#if debug
//print
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << sum[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
#endif
dfs(sum, cnt + 1);
//sum을 prev로 원상 복귀
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum[i][j] = prev[i][j];
}
}
//bis을 초기화.
memset(bis, 0, sizeof(bis));
}//if
}//for j
}//for i
}
void dfs2(int prev[][NUM], int cnt) {
int sum[NUM][NUM];
int bis[NUM][NUM] = { 0 };
if (maxv2 < cnt)
maxv2 = cnt;
//i는 행
for (int i = 0; i < N; i+=1) {
int j = (i+1) % 2;
//j는 열
for (; j < N; j+=2) {
if (prev[i][j] == 0) {
//i,j위치의 비숍으로 이동을 제한한다.
for (int k = 0; k < 4; k++) {
int nr = i;
int nc = j;
while (nr >= 0 && nr < N && nc >= 0 && nc < N) {
bis[nr][nc] = 1;
nr += dir_r[k];
nc += dir_c[k];
}
}
//sum을 prev랑 bis로 고친다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum[i][j] = prev[i][j] | bis[i][j];
}
}
#if debug
//print
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << sum[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
#endif
dfs2(sum, cnt + 1);
//sum을 prev로 원상 복귀
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum[i][j] = prev[i][j];
}
}
//bis을 초기화.
memset(bis, 0, sizeof(bis));
}//if
}//for j
}//for i
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("input.txt", "r", stdin);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int tmp;
cin >> tmp;
arr[i][j] = !tmp;
}
}
int cur[NUM][NUM] = { 0 };
dfs(arr, 0);
dfs2(arr, 0);
cout << maxv+maxv2;
return 0;
}낼해보고 안되면 해설보자..ㅠ
'알고리즘 문제 풀기' 카테고리의 다른 글
| leet code : trapping rain water, 백준 : 히스토그램 6549 (0) | 2020.02.25 |
|---|---|
| 백준 2517번 : 달리기 (0) | 2020.02.25 |
| 백준 2098번: 외판원 순회, 9251번 lcs (0) | 2020.02.14 |
| 백준 : 3176번 도로 네트워크, 11657번 타임머신(벨만포드) (0) | 2020.02.11 |
| 백준 1103번 게임 , 1256번 사전 (0) | 2020.02.10 |