둠치킨
코딩하는 둠치킨
둠치킨

블로그 메뉴

  • 홈
  • 분류 전체보기 (218)
    • BOJ (171)
      • 스택 (14)
      • 큐 (5)
      • 덱 (4)
      • 그래프 (30)
      • 배열 (8)
      • 재귀 (12)
      • 브루트 포스 (2)
      • 그리디 알고리즘 (7)
      • 다이내믹 프로그래밍 (13)
      • 백트래킹 (24)
      • 기하학 (4)
      • 트리 (4)
      • 구현 (14)
      • 수학 (3)
      • 맵 (1)
      • 다익스트라 (2)
      • 누적합 (5)
    • 자료구조 (14)
      • 스택 (3)
      • 큐 (5)
      • 덱 (2)
      • 그래프 (1)
      • 트리 (1)
      • 힙 (1)
      • 정렬 (1)
    • C++ (11)
      • 모두의코드 (2)
      • Effective C++ (3)
      • C++ STL (6)
    • 컴파일러 (1)
    • OS (17)
    • 컴퓨터 구조 (2)
    • Unreal Engine 5 (2)

공지사항

전체 방문자
오늘
어제

인기 글

최근 글

태그

  • BFS
  • boj
  • Bruteforce
  • C
  • C++
  • C++ STL
  • Cache Memory
  • deadlock
  • DFS
  • Effective C++
  • java
  • Mutex
  • next_permutation
  • os
  • Process
  • rotate
  • semaphore
  • spin lock
  • STL
  • STL C++
hELLO · Designed By 정상우.
둠치킨

코딩하는 둠치킨

2239번: 스도쿠 (BOJ C/C++)
BOJ/백트래킹

2239번: 스도쿠 (BOJ C/C++)

2022. 2. 10. 22:31

2239번: 스도쿠

사용 언어: C++

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

풀이

#include <iostream>
#include <string>
#define MAX 9
using namespace std;

string sudoku[MAX];
int row[MAX][MAX]; //열, 1 ~ 9
int col[MAX][MAX]; //행, 1 ~ 9
int square[MAX][MAX]; //3 * 3 박스 idx, 1 ~ 9

int make3by3(int y, int x)
{
	return (y/3)*3 + x/3;
}

void Back_Tracking(int cnt)
{
	if(cnt==81)
	{
		for(int i=0; i<MAX; i++)
		{
			for (int j=0; j<MAX; j++)
				cout << sudoku[i][j];
			cout << "\n";
		}
		exit(0); //사전식으로 앞서는 답 출력
	}

	int y = cnt / 9;
	int x = cnt % 9;

	//칸이 채워져 있으면 넘어감
	if (sudoku[y][x] != '0')
		Back_Tracking(cnt+1);
	
	//칸이 안 채워져 있고
	else
	{
		for (int k=1; k<=MAX; k++)
		{
			//가로줄에 없고 세로줄에 없고 정사각형 안에 없어야 함.
			if (!col[x][k] && !row[y][k] && !square[make3by3(y,x)][k])
			{
				sudoku[y][x] = k + '0'; //필요한 숫자 채워 넣음
				col[x][k] = row[y][k] = square[make3by3(y,x)][k] = 1; //있다고 표시
				Back_Tracking(cnt + 1);
				sudoku[y][x] = '0'; //리셋
				col[x][k] = row[y][k] = square[make3by3(y,x)][k] = 0; //리셋
			}
		}
	}
}

int main(void)
{
	for (int i = 0; i < MAX; i++)
	{
		cin >> sudoku[i];
		for (int j = 0; j < MAX; j++)
		{
			if (sudoku[i][j] != '0')
			{
				int num = sudoku[i][j] - '0';
				col[j][num] = row[i][num] = square[make3by3(i,j)][num] = 1;
			}
		}
	}

	Back_Tracking(0);

	return 0;
}
저작자표시 (새창열림)

'BOJ > 백트래킹' 카테고리의 다른 글

15651번: N과 M (3) (BOJ C/C++)  (0) 2022.09.01
15650번: N과 M (2) (BOJ C/C++)  (0) 2022.09.01
1182번: 부분수열의 합 (BOJ C/C++)  (0) 2022.09.01
9663번: N-Queen (BOJ C/C++)  (0) 2022.08.31
15649번: N과 M (1) (BOJ C/C++)  (0) 2022.02.10
    'BOJ/백트래킹' 카테고리의 다른 글
    • 15650번: N과 M (2) (BOJ C/C++)
    • 1182번: 부분수열의 합 (BOJ C/C++)
    • 9663번: N-Queen (BOJ C/C++)
    • 15649번: N과 M (1) (BOJ C/C++)
    둠치킨
    둠치킨
    코딩 공부를 위한 코딩 블로그 기록 일기

    티스토리툴바