[백준 3967] 매직 스타

그러니까 누가 return true 빼먹으래,,, ?

https://www.acmicpc.net/problem/3967

3967번: 매직 스타

#include <cstdio>
#include <vector>
#include <string>
using namespace std;

int used[12 + 2];
char map_in[5 + 2][9 + 2];
int board[5 + 2][9 + 2];	// 계산하기 편하려고 숫자로 바꿔줄 것임

struct _st
{
	int x;
	int y;
};

vector<_st> B;	// x로 주어진 곳의 좌표 


void debug()
{
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			printf("%d ", board[i][j]);
		}
		printf("\n");
	}
}


void input()
{
	for (int i = 0; i < 5; i++) {
		scanf("%s", &map_in[i]);
		for (int j = 0; j < 9; j++) {
			if (map_in[i][j] == 'x') {
				B.push_back({ i, j });
				board[i][j] = -1;
			}
			else if (map_in[i][j] == '.') board[i][j] = 0;
			else {
				board[i][j] = map_in[i][j] - 'A' + 1;
				used[board[i][j]] = 1;	// 숫자 쓴거 표시
			}
		}
	}
}


bool chk()
{
	if (board[0][4] + board[1][3] + board[2][2] + board[3][1] != 26) return false;
	if (board[0][4] + board[1][5] + board[2][6] + board[3][7] != 26) return false;
	if (board[1][1] + board[1][3] + board[1][5] + board[1][7] != 26) return false;
	if (board[3][1] + board[3][3] + board[3][5] + board[3][7] != 26) return false;
	if (board[1][1] + board[2][2] + board[3][3] + board[4][4] != 26) return false;
	if (board[1][7] + board[2][6] + board[3][5] + board[4][4] != 26) return false;
	return true;		// 위에 조건문이 다 제껴지면 마지막엔 true를 리턴해야 한다.
}


bool DFS(int n)
{
	if (n == B.size()) {
		return chk();
	}
	
	for (int i = 1; i <= 12; i++) {
		if (used[i]) continue;			// 이미 사용한 숫자라면 스루 
		board[B[n].x][B[n].y] = i;
		used[i] = 1;
		if (DFS(n + 1)) return true;
		used[i] = 0;	// 원복 
	}
	return false;
}


void output()
{
	//debug();
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == 0) printf(".");
			else printf("%c", board[i][j] - 1 + 'A');
		}
		printf("\n");
	}
}




int main()
{
	input();
	DFS(0);		// 0번째 빈칸부터 채움 
	output();
	return 0;
}

이건 마치 제 2의 스도쿠라고 해야할까,,, ? 

코드 전체 구조가 매우 유사하다.

 

// input( ) 함수

입력받을 때 수가 채워지지 않은 곳(x)은 -1로 , 매직스타의 형태를 만들기 위해 사용한 문자(.)는 0으로, 나머지 알파벳은 "문자 - 'A' + 1"을 하여 숫자로 변환해주었다. 굳이 안해도 되는 과정이지만 이렇게 해주면 나중에 chk( ) 함수에서 더하기가 편하다. 

그리고 채워야 할 곳의 좌표들은 벡터B에 받아주었다. 해당 벡터의 인덱스로 DFS 함수를 돌리면서 빈칸을 채워줄 것이다. 

 

 

// DFS( ) 함수

파라미터는 "몇 번째 벡터를 채울 것인지" 이다. 

매직 스타를 만드는 방법 중 사전순으로 가장 앞서는 방법을 출력해달라고 했으므로, 빈칸을 채워넣을 수를 1부터 12까지 순차적으로 확인한다. 

만약 이미 사용한 숫자라면 스루( if (used[i]) continue )하고, 그게 아니면 해당 숫자를 board에 채워넣는다. 그리고 해당 숫자를 사용했으므로 used배열의 i 숫자를 사용했다는 표시를 해준다. 

 

만약 DFS를 벡터에 저장된 빈칸의 좌표 수 + 1 만큼 돌렸으면(B.size()) chk( ) 배열을 호출하여 현재 생성된 보드판이 매직 스타의 조건을 만족하는지 확인한다. 

 

 

// chk( ) 함수

만약, 한 줄이라도 더하여 26이 만들어지지 않으면 false를 리턴한다.

모든 줄이 더하여 26을 만족하면 반드시 true를 리턴하도록 한다. (이거 빼먹으면 테케는 잘 나오는데 9%에서 틀렸다고 나온다.. 뭔가 했네... ) 

이러한 리턴 조건 빠트리지 않도록 주의해야 겠다. 

 

 

 

// output( ) 함수

숫자배열인 board[i][j]가 0이면 " . "을 출력한다. 

그렇지 않으면 이제 x는 없고 모두 알파벳 대문자가 채워진 상태이기 때문에, "숫자 - 1 + 'A'" 로 변환하여 문자로 출력한다.