[BOJ] ์Šค๋„์ฟ (2580)

[๋ฐฑ์ค€(BOJ)] ์Šค๋„์ฟ (2580) C++

๋ฌธ์ œ : BOJ_2580๋ฒˆ ์Šค๋„์ฟ 

์ž…์ถœ๋ ฅ ํ˜•์‹๋งŒ ์‚ด์ง ๋‹ค๋ฅธ ๊ฐ™์€ ๋ฌธ์ œ๋กœ BOJ_2239๋ฒˆ ์Šค๋„์ฟ ๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

๋ฌธ์ œ ์„ค๋ช…

๋ฐฑํŠธ๋ž˜ํ‚น, dfs

์™„์„ฑ๋˜์ง€ ์•Š์€ ์Šค๋„์ฟ ๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ์ด๋ฅผ ์™„์„ฑํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
์Šค๋„์ฟ ์˜ ์ˆ˜๊ฐ€ ํ™•์ •๋˜์ง€ ์•Š์€ ๊ณณ์€ 0์œผ๋กœ ์ž…๋ ฅ๋˜์–ด ์žˆ๊ณ , ์ด 0๋“ค์„ ์ „๋ถ€ ์ฑ„์šด ์Šค๋„์ฟ ํŒ์„ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
๋ฌธ์ œ๋Š” ์ŠคํŽ˜์…œ ์ €์ง€์ด๋ฏ€๋กœ, ํ•˜๋‚˜์˜ ๊ฒฝ์šฐ๊ฐ€ ์•„๋‹Œ ์—ฌ๋Ÿฌ ๊ฒฝ์šฐ๊ฐ€ ๋‹ต์ด ๋  ์ˆ˜ ์žˆ๋Š” ์Šค๋„์ฟ ๋Š” ๊ทธ์ค‘ ํ•˜๋‚˜๋ฅผ ์ถœ๋ ฅํ•˜๋ฉด ์ •๋‹ต ์ฒ˜๋ฆฌ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.
dfs์™€ ๋ฐฑํŠธ๋ž˜ํ‚น์„ ์ด์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.


Solution

์ž…๋ ฅ ๋ฒˆํ˜ธ๊ฐ€ 0์ธ ๊ณณ์˜ ์ขŒํ‘œ๋“ค์„ ํ•˜๋‚˜ํ•˜๋‚˜ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค.
์ €์žฅ๋œ ์ขŒํ‘œ๋ฅผ ํ•˜๋‚˜์”ฉ dfs๋กœ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค.
์ด๋•Œ ํ˜„์žฌ ์ˆœํšŒ ์ค‘์ธ ๊ณณ์— ๋งž๋Š” ๋ฒˆํ˜ธ๊ฐ€ ์žˆ์œผ๋ฉด ๋‹ค์Œ ์ˆœํšŒ๋กœ ์ง„ํ–‰ํ•˜๊ณ , 1~9 ๋ชจ๋“  ๋ฒˆํ˜ธ๊ฐ€ ๋‹ค ์ค‘๋ณต๋œ๋‹ค๋ฉด ์ด์ „ ์ˆœํšŒ๋กœ ๋Œ์•„๊ฐ€์„œ ๋‹ค๋ฅธ ์ˆ˜๋ฅผ ์ž…๋ ฅํ•˜๋Š” ๋ฐฑํŠธ๋ž˜ํ‚น ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
0์ธ ๊ฐ ์ขŒํ‘œ๋ฅผ ๋Œ๋ฉด์„œ ์Šค๋„์ฟ ์˜ ๊ทœ์น™์— ๋งž๊ฒŒ ์ขŒํ‘œ์˜ ์„ธ๋กœ์ถ•๋“ค, ๊ฐ€๋กœ์ถ•๋“ค์— ์ธ์ ‘ํ•œ ๊ณณ๋“ค์˜ ๋ฒˆํ˜ธ๋ฅผ ํ™•์ธํ•˜์—ฌ ์ฒดํฌํ•ฉ๋‹ˆ๋‹ค.
๋˜ํ•œ ๊ฐ ์ขŒํ‘œ๊ฐ€ ์†ํ•œ 3*3 ์‚ฌ์ด์ฆˆ์˜ ์‚ฌ๊ฐํ˜•๋„ ์ˆœํšŒํ•˜๋ฉฐ ๋ฒˆํ˜ธ๋ฅผ ํ™•์ธํ•˜๊ณ  ์ฒดํฌํ•ด ์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.


Description

  • 0์ธ ๊ฐ ์ขŒํ‘œ๋Š” vector<pair<int, int>> zeroPoint๋ฅผ ์‚ฌ์šฉํ•ด ์ €์žฅํ–ˆ์Šต๋‹ˆ๋‹ค.
  • dfs์˜ ์ธ์ž๋Š” (์ˆœํšŒํ•  ๋‹ค์Œ x์ขŒํ‘œ, ์ˆœํšŒํ•  ๋‹ค์Œ y์ขŒํ‘œ, ์ˆœํšŒ ํšŸ์ˆ˜)๋กœ ๋งŒ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค.
  • ๊ฐ ์ˆœํšŒ๋งˆ๋‹ค bool possible[10]์˜ boolํ˜• ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด์„œ ๊ฐ€๋Šฅ, ๋ถˆ๊ฐ€๋Šฅํ•œ ์ˆ˜๋ฅผ ์ฒดํฌํ–ˆ์Šต๋‹ˆ๋‹ค.

#include <iostream>
#include <vector>
using namespace std;
int map[10][10];
vector<pair<int, int>> zeroPoint;
int zeroPointCnt;
bool endSwc = false;
void dfs(int x, int y, int cnt) {
	if (endSwc) return;
	bool possible[10];
	for (int i = 1; i <= 9; i++) possible[i] = true;
	for (int i = 1; i <= 9; i++) {
		if (y == i) continue;
		possible[map[x][i]] = false;
	}
	for (int i = 1; i <= 9; i++) {
		if (x == i) continue;
		possible[map[i][y]] = false;
	}
	int xSt = 0;
	if (x % 3 == 0) xSt = x - 3;
	else xSt = x - (x % 3);
	int ySt = 0;
	if (y % 3 == 0) ySt = y - 3;
	else ySt = y - (y % 3);
	for (int i = xSt + 1; i <= xSt + 3; i++) {
		for (int j = ySt + 1; j <= ySt + 3; j++) {
			if (x == i && y == j) continue;
			possible[map[i][j]] = false;
		}
	}
	for (int i = 1; i <= 9; i++) {
		if (possible[i]) {
			if (cnt == zeroPointCnt) {
				map[x][y] = i;
				for (int i = 1; i <= 9; i++) {
					for (int j = 1; j <= 9; j++) {
						cout << map[i][j] << ' ';
					}
					cout << '\n';
				}
				endSwc = true;
				return;
			}
			else {
				map[x][y] = i;
				dfs(zeroPoint[cnt].first, zeroPoint[cnt].second, cnt + 1);
				map[x][y] = 0;
			}
		}
	}
}
int main(void) {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				zeroPoint.push_back({ i,j });
				zeroPointCnt++;
			}
		}
	}
	dfs(zeroPoint[0].first, zeroPoint[0].second, 1);
	return 0;
}