[JAVA] 백준 2580 스도쿠

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

2580번: 스도쿠

 

- 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 ㅇ리부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있음 

 

 

 

 

 

https://commons.wikimedia.org/wiki/File:Sudoku_solved_by_bactracking.gif

 

 

- 나머지 빈 칸을 채우는 방식은 다음과 같음 

 

 1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

 2. 굵은 선으로 구분되어 있는 3*3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

 

- 게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 떄 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램 

 

- 스도쿠 판의 빈 칸의 경우에는 0이 주어짐 

 

 

풀이 과정 

 

[백준] 2580번 : 스도쿠 - JAVA [자바] (tistory.com)

[백준] 2580번 : 스도쿠 - JAVA [자바]

[백준] 2580번 : 스도쿠 (백트래킹 골드Ⅳ) - Python — 채야미랑 꽁냥꽁냥 (tistory.com)

[백준] 2580번 : 스도쿠 (백트래킹 골드Ⅳ) - Python

 

 

- int 형 2차원 배열을 사용하여, 첫 번째 인덱스는 행을, 두 번째 인덱스는 열을 의미하는 스도쿠 배열 생성 

- 탐색하려는 값을 value라고 정함

 

조건 체크 

1) 같은 열의 다른 행에 넣으려는 수가 이미 있는지 

 

2) 같은 행의 다른 열에 넣으려는 수가 이미 있는지 

 

3) 넣으려는 수가 3*3 영역에 이미 있는지 

  -> 3*3의 위치는 각 칸의 위치는 왼쪽 위를 기준으로 할 것이기 때문에 나눗셈을 통해 나머지를 버린 뒤 다시 3을 곱하여 0,3,6 중 하나가 나올 수 있도록 함 

( [0][0], [0][3], [0][6], [3][0], [3][3], [3][6], [6][0], [6][3], [6][6] )

 

- 배열을 (0,0)부터 순회하며 만약 탐색하는 칸이 0(빈칸)일 경우 반복문을 통해 1~9까지의 수들 중 조건 검사 함수를 통해 만족하게 된다면 재귀호출을 해줌 

 

- 재귀 호출하면서 모든 값이 다 채워지게 된다면 배열을 출력한 뒤 시스템을 종료해야 함 

- System.exit(0)를 사용 

 

 

정답

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  final static int SIZE = 9;
  static int[][] sudoku = new int[SIZE][SIZE];
  static BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
  
    
  public static boolean check(int row, int col, int value)
  {
      //같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사 
      for(int i=0; i<9; i++)
      {
          if(sudoku[row][i] == value)
          {
              return false;
          }
      }
      
      //같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
      for(int i=0; i<9; i++)
      {
          if(sudoku[i][col] == value)
          {
              return false;
          }
      }
      
      //3*3칸에 중복되는 원소가 있는지 검사 
      int set_row = (row/3)*3; //value가 속한 3*3의 행의 첫 위치
      int set_col = (col/3)*3; //value가 속한 3*3의 열의 첫 위치
      
      for(int i=set_row; i<set_row+3; i++)
      {
          for(int j=set_col; j<set_col+3; j++)
          {
              if(sudoku[i][j] == value)
              {
                  return false;
              }
          }
      }
      
      return true; 
  }
  
  public static void dfs(int row, int col) throws IOException
  {
	  //해당 행이 다 채워졌을 경우 다음 행의 첫 번째 열부터 시작
	  if(col == SIZE)
	  {
		  dfs(row+1,0);
		  return;
	  }
	  
	  //행과 열이 모두 채워졌을 경우 출력 후 종료 
	  if(row == SIZE)
	  {
		  StringBuilder sb = new StringBuilder();
		  for(int i=0; i<SIZE;i++)
		  {
			  for(int j=0; j<SIZE; j++)
			  {
				  sb.append(sudoku[i][j]).append(' ');
			  }
			  sb.append('\n');
		  }
		  System.out.println(sb);
		  
		  System.exit(0);
	  }
	  
	  //만약 해당 위치의 값이 빈칸이라면 1부터 9까지 중 가능한 수 탐색
	  if(sudoku[row][col] ==0)
	  {
		  for(int i=1; i<=SIZE; i++)
		  {
			  //i값이 중복되지 않는지 검사 
			  if(check(row,col,i))
			  {
				  sudoku[row][col]=i;
				  dfs(row,col+1);
			  }
		  }
		  sudoku[row][col] = 0;
		  return;
	  }
	  dfs(row,col+1);
  }
    
  public static void main(String[] args) throws IOException
  {
	  
      for(int i=0; i<SIZE; i++)
      {
    	  StringTokenizer st = new StringTokenizer(br.readLine());
          for(int j=0; j<SIZE; j++)
          {
              sudoku[i][j] = Integer.parseInt(st.nextToken());
          }
      }
      
      dfs(0,0); //(0,0)부터 시작 
      

  }
 
  
}