문제 url:
스도쿠
문제:
🤔 문제 알아보기
스도쿠 다들 한번쯤은 풀어봤을 것이다. 9x9크기의 스도쿠 판에서 빈칸에 조건에 맞는 수를 넣어 모든 칸이 꽉 채워지면 스도쿠가 완성된다.
이번 문제에서는 조건이 3가지가 존재한다.
- 가로줄에는 1부터 9까지 중복없이 한 번만 나타나야 한다.
- 세로줄에는 1부터 9까지 중복없이 한 번만 나타나야 한다.
- 굵은선으로 표시된 3x3크기의 정사각형 안에는 1부터 9까지 중복없이 한번만 나타나야 한다.
그럼 조건을 알아봤으니, 해당 조건에 대한 풀이를 먼저 알아보도록 하자,
static boolean possibility(int row, int col, int target) {
/*
* 열을 기준으로 중복값 검토
* 중복값이 존재한다면 false 반환
*/
for(int i = 0; i < 9; i++) {
if(arr[row][i] == target) {
return false;
}
}
/*
* 행을 기준으로 중복값 검토
* 중복값이 존재한다면 false 반환
*/
for(int i = 0; i < 9; i++) {
if(arr[i][col] == target) {
return false;
}
}
/*
* 중간 정사각형(3*3크기) 안에 중복값 검토
* 중복값이 존재한다면 false 반환
* 만약 값이 0,1,2 -> 0이 입력
* 만약 값이 3,4,5 -> 1 * 3 = 3이 입력
* 만약 값이 6,7,8 -> 2 * 3 = 6이 입력
*/
int new_row = (row / 3) * 3;
int new_col = (col / 3) * 3;
/*
* 위에서 구한 값이 곧 첫번째 값을 의미
* 범위는 3x3 크기이기에 초기값 +3 범위까지 반복
*/
for(int i = new_row; i < new_row + 3; i++) {
for(int j = new_col; j < new_col + 3; j++) {
if(arr[i][j] == target) {
return false;
}
}
}
/*
* 세 가지 조건을 모두 통과하면 중복값이 존재하지 않기에 true를 반환
*/
return true;
}최대한 주석으로 설명을 했기 때문에 따라가는 데 문제는 없을 것이지만
간략하게 살펴보자면
target은 해당값이 중복값인지 아닌지를 판별하기 위해 받는 파라미터값이다.
아마 가로, 세로까지 구하는 건 코드로나 텍스트로나 쉽게 이해가 될 것이다.
하지만, 3x3 정사각형안에서 타겟값을 찾는건 같이 알아보자,
int new_row = (row / 3) * 3;
int new_col = (col / 3) * 3;
/*
* 위에서 구한 값이 곧 첫번째 값을 의미
* 범위는 3x3 크기이기에 초기값 +3 범위까지 반복
*/
for(int i = new_row; i < new_row + 3; i++) {
for(int j = new_col; j < new_col + 3; j++) {
if(arr[i][j] == target) {
return false;
}
}
}먼저, 새로운 초기값을 받기 위해 new_row, new_col 변수를 정의한다.
row 혹은 col에 0,1,2 값에 나누기 3을 하면 몫이 0이다. 0이기 때문에 3을 곱해도 0
row 혹은 col에 3,4,5 값이 들어오고 이를 나누기 3을 하면 몫이 1이 된다. 여기서 3을 곱하면 3으로, 초기값이 3부터 시작하게 세팅할 수 있다.
row 혹은 col에 6,7,8 값이 들어오고 이를 나누기 3을 하면 몫이 2가 되고, 이를 3을 곱하면 6으로, 초기값이 6부터 시작하게 세팅할 수 있다.
자 그럼 이렇게 구한 값을 가지고, 반복문을 동작하면
우리가 원하는 3x3크기의 정사각형만큼 target값을 구할 수 있다.
자 주요 조건은 어느정도 설명했다. 이제 코드와 함께 더 알아보자
🐱👤 실제 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
arr = new int[9][9];
/*
* 배열 입력을 위한 for문
*/
for(int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < 9; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 0);
}
static void dfs(int x, int y) {
/*
* 열이 9까지 오면, 다음 행으로 이동하도록
*/
if(y == 9) {
dfs(x + 1, 0);
return;
}
/*
* 행이 9까지 왔다는 건, 현재 스도쿠 판이 꽉 찼다는 의미
* 즉, 조건에서 하나의 스도쿠만 출력하라고 했기 때문에
* 가장 먼저 나오는 스도쿠를 출력 후 시스템을 종료(System.exit(0))
*/
if(x == 9) {
StringBuilder sbd = new StringBuilder();
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
sbd.append(arr[i][j]).append(" ");
}
sbd.append("\n");
}
System.out.println(sbd);
System.exit(0);
}
/*
* 현재 칸이 비어있다면, 해당 값을 채우기 위해
* 3가지 조건에 따라 중복되지 않은 값을 입력
*/
if(arr[x][y] == 0) {
for(int i = 1; i <= 9; i++) {
if(possibility(x, y, i)) {
/*
* 현재 중복되는 값이 아니기 때문에
* 해당 좌표에 target값을 입력
*/
arr[x][y] = i;
/*
* col을 더해서 다음 0이 위치한 곳으로 이동
*/
dfs(x, y + 1);
}
}
/*
* 왜 뜬금없이 0을 주냐??
* 여기까지 왔다는 것은, 이미 위에서 스도쿠가 맞춰지지 않은 상태에서
* return을 했기 때문에 즉, 잘못된 값을 넣었다는 의미로 다시 초기값으로 세팅
* 또한 return을 통해 해당 0이 채워지기 이전의 상태로 되돌아가서
* 다시 해당 좌표로 와 0을 채우도록 함.
* 근데, 만약 해당 값이 맞다면!!
* 결국 스도쿠를 채워서 출력한 다음 시스템이 종료되기에 0이 되지 않음
*/
arr[x][y] = 0;
return;
}
dfs(x, y+1);
}
static boolean possibility(int row, int col, int target) {
/*
* 열을 기준으로 중복값 검토
* 중복값이 존재한다면 false 반환
*/
for(int i = 0; i < 9; i++) {
if(arr[row][i] == target) {
return false;
}
}
/*
* 행을 기준으로 중복값 검토
* 중복값이 존재한다면 false 반환
*/
for(int i = 0; i < 9; i++) {
if(arr[i][col] == target) {
return false;
}
}
/*
* 중간 정사각형(3*3크기) 안에 중복값 검토
* 중복값이 존재한다면 false 반환
* 만약 값이 0,1,2 -> 0이 입력
* 만약 값이 3,4,5 -> 1 * 3 = 3이 입력
* 만약 값이 6,7,8 -> 2 * 3 = 6이 입력
*/
int new_row = (row / 3) * 3;
int new_col = (col / 3) * 3;
/*
* 위에서 구한 값이 곧 첫번째 값을 의미
* 범위는 3x3 크기이기에 초기값 +3 범위까지 반복
*/
for(int i = new_row; i < new_row + 3; i++) {
for(int j = new_col; j < new_col + 3; j++) {
if(arr[i][j] == target) {
return false;
}
}
}
/*
* 세 가지 조건을 모두 통과하면 중복값이 존재하지 않기에 true를 반환
*/
return true;
}
}
이번 문제는 필자도 여러번 이해해보고자, 주석을 조금 빡세게 자세히 적었다. 이전과 같이 코드를 나눠서 풀이를 하고자 하였는데, 코드도 많고, 이를 분해해서 보면 복잡해질 수 있다 판단해 주석으로 설명을 대체하고자 한다.
🤢 회고
골드 문제가 이제 한 개씩 나오고 있다.
더닝크루거 효과라고 아는가?
필자는 브론즈 문제에서 실버 문제로 넘어갈 때 이 정도 속도와 공부면 조금 있으면 코테를 봐도 되는 수준까지 가지 않겠는가 하는 생각과 자신감으로 가득찼었다.
근데, 재귀와 백트래킹 문제를 풀면서 이 길이 내 길인가 의심이 들기도 하고, 이렇게 해서 코테는 무슨 한 문제라도 풀고 나올련가 하는 걱정이 앞서며 필자의 실력을 다시 초기화 시키는 작업을 하고 있다.
알고리즘 공부를 처음 시작한지 곧 2달이 다 되가는 시점에서 필자의 성장이 어디까지 갈 수 있을까 의문을 가진다.
하지만! 알고리즘 공부는 빡세게 1년은 해야 완성된다고 익히 들었다. 이제 2달을 한 뉴비한테는 포기하기 이른 시간... 좀 더 분발해서 플레까지 이번년도 안에 찍어보자
💜 참고자료
