백준 2580번 스도쿠, 1799번 비숍

알고리즘 문제 풀기

백준 2580번 스도쿠, 1799번 비숍

studying develop 2020. 2. 24. 12:21

스도쿠 ( 백트레킹 문제를 더 고민해보자!!, 이전에 백트레킹인줄 몰라서 틀린게 좀 있는거 같다. 카카오 원판 순회?)

음 완전탐색해야 될거 같다. 가능한 놈들을 추려서 결국에 가능한 한가지 경우만 도출하면 될거같은데 구현 방법이 떠오르지 않는다.

후보를 어떻게 저장해야 될까, 각 칸마다 저장하는건 올바르지 못한거 같다. 각 행,열 마다 후보들을 저장해놓자.

그리고 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

현재글백준 2580번 스도쿠, 1799번 비숍

swift, python, java, 아이폰 앱 개발, 안드로이드 앱 개발, 서버 공부, 머신러닝 공부, 그래픽스 공부 등등 기록입니다.

IOS, Django, 스택, node.js, SWIFT, URLSessionTask, 함수형 프로그래밍, application.properties, present, 스위프트, 릿코드, 프로그래머스, 파이썬, watchConnectivity, 스프링부트, 안드로이드, 면접 대비, 알고리즘, 백준, leetcode,

Today :
Yesterday :

개인적으로 공부한 내용을 정리중입니다.