본문 바로가기
카테고리 없음

백준 2239 c++ "스도쿠" -PlusUltraCode-

by PlusUltraCode 2025. 7. 1.

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

 

[필자 사고]

백트래킹 및 구현 문제다.

ㅇㅣ 문제만의 독특한 매력은 0인 구간을 idx로 따로 넣어서 해당 idx관련 백트래킹만 수행하면 된다.

각 for문 범위는 1~9라는 숫자들을 넣은 형태로 백트래킹을 수행한다.

 

또한 필자가 개인적으로 배운 기술은 int startSero 처리 로직이다.

특정 인덱스의 시작과 끝을 알려면 

int startSero = sero/3*3 을 하게 되면 원하는 시작 idx를 바로 구할 수 있었다. 

옛날에는 하드코딩 했었는데 좋은 배움이 되었다.

[코드 해설]

vector<vector<int>> arr

  • 9×9 스도쿠 보드를 저장하는 2차원 벡터입니다.
  • 각 요소는 0~9의 숫자 중 하나를 저장하며, 0은 빈 칸을 의미합니다.

vector<pair<int, int>> idxArr

  • 스도쿠 보드에서 0으로 비어 있는 칸의 좌표들을 저장하는 리스트입니다.
  • 백트래킹 시 이 리스트의 인덱스를 따라 빈 칸을 순차적으로 채웁니다.

void Input()

  • 표준 입력으로 9줄의 문자열(숫자 9개)을 받아서 arr에 숫자로 저장합니다.
  • 동시에 숫자가 0인 칸의 좌표를 idxArr에 저장해둡니다.
  • 입력값이 문자열이므로 str[k] - '0'으로 정수 변환합니다.
  • arr.assign(9, vector<int>(9))을 통해 9×9 배열로 초기화합니다.

bool isValid(int sero, int garo, int num)

  • 주어진 (sero, garo) 좌표에 num을 넣었을 때 스도쿠 규칙을 만족하는지 검사합니다.
  • 가로(행), 세로(열), 그리고 3×3 박스에 동일한 숫자가 존재하면 false를 반환합니다.
  • 조건을 모두 통과하면 true를 반환합니다.

bool firstFlag

  • 해를 찾은 뒤 더 이상 탐색하지 않도록 하는 플래그입니다.
  • 첫 번째 정답만 출력하고 탐색을 멈추기 위해 사용됩니다.

void Print()

  • 현재 보드 상태인 arr를 9줄로 출력합니다.
  • 각 줄에는 9개의 숫자가 붙어서 출력됩니다.

void backTracking(int idx)

  • 백트래킹 알고리즘의 핵심 함수입니다.
  • idxArr의 idx번째 빈 칸에 대해 1~9 중 가능한 숫자를 하나씩 시도합니다.
  • isValid()로 숫자가 유효한지 검사하고, 유효하면 보드에 넣고 재귀 호출합니다.
  • 이후 다시 0으로 되돌려 백트래킹을 수행합니다.
  • idx == idxArr.size()가 되면 모든 빈 칸이 채워졌으므로 정답을 출력하고 firstFlag = true로 탐색을 중지합니다.

void Game_Start()

  • 백트래킹 탐색을 시작하는 진입 함수입니다.
  • 항상 backTracking(0)으로 시작합니다.

int main()

  • 프로그램의 시작점입니다.
  • Input()을 호출해 데이터를 입력받고, Game_Start()로 스도쿠 풀이를 시작합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<vector<int>> arr;
vector<pair<int, int>> idxArr;

void Input() {

	arr.assign(9, vector<int>(9));

	for (int i = 0; i < 9; i++) {
		string str;
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			arr[i][k] = str[k]-'0';
			if (arr[i][k]==0)idxArr.push_back({ i,k });
		}
	}
}

bool isValid(int sero, int garo, int num) {
	for (int i = 0; i < 9; i++) {
		if (arr[sero][i] == num)return false;
	}

	for (int i = 0; i < 9; i++) {
		if (arr[i][garo] == num)return false;
	}

	int startSero = sero / 3 * 3;
	int startGaro = garo / 3 * 3;

	for (int i = startSero; i < startSero + 3; i++) {
		for (int k = startGaro; k < startGaro + 3; k++) {
			if (arr[i][k] == num)return false;
		}
	}
	return true;
}

bool firstFlag = false;

void Print() {
	for (int i = 0; i < 9; i++) {
		for (int k = 0; k < 9; k++) {
			cout << arr[i][k];
		}
		cout << "\n";
	}
}

void backTracking(int idx) {
	if (firstFlag) return;

	if (idx == idxArr.size()) {
		Print();
		firstFlag = true;
		return;
	}

	int sero = idxArr[idx].first;
	int garo = idxArr[idx].second;

	for (int i = 1; i <= 9; i++) {
		if (isValid(sero, garo, i) == false)continue;
		arr[sero][garo] = i;
		backTracking(idx + 1);
		arr[sero][garo] = 0;
	}
}

void Game_Start() {
	backTracking(0);
}

int main(void) {
	Input();
	Game_Start();
}

티스토리툴바