코드 복사/붙여넣기 하는 당신이 아름답습니다.

2580 : 스도쿠

풀이

태양을 의논하는 거룩한 이야기는 항상 태양을 등진 곳에서만 비롯하였다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;

struct ABC { int x, y, z; };
int a[9][9], x[9], y[9], z[9];
vector<ABC> p;

void dfs(int now) {
	if (now == p.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) printf("%d ", a[i][j]);
			puts("");
		}
		exit(0);
	}

	int nx = p[now].x, ny = p[now].y, nz = p[now].z;
	for (int i = 1; i <= 9; i++) {
		if (x[nx] & (1 << i) || y[ny] & (1 << i) || z[nz] & (1 << i)) continue;
		a[nx][ny] = i, x[nx] |= (1 << i), y[ny] |= (1 << i), z[nz] |= (1 << i);
		dfs(now + 1);
		a[nx][ny] = 0, x[nx] &= ~(1 << i), y[ny] &= ~(1 << i), z[nz] &= ~(1 << i);
	}
}

int main() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			scanf("%d", &a[i][j]);
			if (!a[i][j]) {
				p.push_back({ i,j,(i/3)*3+j/3 });
				continue;
			}
			x[i] |= (1 << a[i][j]);
			y[j] |= (1 << a[i][j]);
			z[(i/3)*3+j/3] |= (1 << a[i][j]);
		}
	}

	dfs(0);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-09-26 15:23

Read more posts by this author