[백준] 2580 - 스도쿠 (JAVA)

1. 소요시간 : 1시간
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 백트래킹
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/2580
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

백트래킹을 사용했다.

2. 사고과정

우선 N-Queen 문제와 굉장히 비슷하다고 생각해서 시간이 오래걸리더라도 혼자 풀어보려고 노력했다.
백트래킹을 이용해서 풀어보려고 했는데 40분 째까지 풀지 못해서 다른 사람의 풀이를 보고 풀게 되었다.
그런데 나는 우선 ArrayList 에 map[i][j] 가 0인 곳의 좌표를 기억해 놓은 다음에 탐색을 했는데 생각보다 그렇게 한 사람이 많이 없었다.
대부분 행을 먼저 처리하고, 그 다음에 열을 처리하는 식의 로직이었기에, 내 풀이 방법 또한 바꿔야 하나 싶었지만 다행히 나와 비슷하게 풀이를 한 곳을 찾아서 그 풀이를 보고 많이 배웠다.

3. 풀이과정

1. map[i][j] 가 0인 좌표를 ArrayList에 저장
2. map[i][j] 가 0인 좌표를 check 메소드로 체크. 만약 이 좌표에 1~9의 숫자를 쓸 수 있다면 1부터 대입하고 depth를 늘려서 탐색한다.
3. 그리고 최종적으로 depth 가 list.size() 가 되면 출력한다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {

	static int map[][]=new int[9][9];

	static ArrayList<Integer[]> list=new ArrayList<>();
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		for(int i=0;i<map.length;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<map.length;j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==0)
					list.add(new Integer[] {i,j});
			}
		}

		dfs(0);
		
	}
	public static void dfs(int depth) {
		if(depth==list.size()) {
			for(int i=0;i<map.length;i++) {
				for(int j=0;j<map.length;j++) {
					System.out.print(map[i][j]+" ");
				}
				System.out.println();
			}
			System.exit(0);
		}
		
		
		int row=list.get(depth)[0];
		int col=list.get(depth)[1];
		
		for(int i=1;i<=9;i++) {
			if(check(row,col,i)) {
				map[row][col]=i;
				dfs(depth+1);
				map[row][col]=0;
			}
		}
		
		
		
		
	}
	public static boolean check(int row,int col,int value) {
		for(int i=0;i<map.length;i++) {
			if(map[row][i]==value) return false;
			if(map[i][col]==value) return false;
		}
		
		int range1=row/3*3;
		int range2=col/3*3;
		
		for(int i=range1;i<range1+3;i++) {
			for(int j=range2;j<range2+3;j++) {
				if(map[i][j]==value) return false;
			}
		}
		
		
		return true;
	}
}

5. 결과

6. 회고

이 짧은 70줄 짜리 정도의 코드에도 얼마나 많은 기술들이 들어가 있는지 .. 옛날에는 그냥 무지막지하게 100줄 ~ 200줄 짜리 코드를 보면 우와... 하면서 감탄했지만 요즘에는 그보다 짧고 효과적인 50줄 짜리 코드를 보면서 더 대단하다고 느끼는 것 같다.

이 문제를 풀면서 알게 된 것은 우선
1. 3 x 3 좌표의 내가 속한 그룹을 찾는 기술이다. 나는 무지막지하게 내 행, 열을 보고 if(row>=0&&row<=2&&col>=0&&col<=2) 같은 if 문을 9개 작성해서 내가 속한 좌표의 그룹을 알았지만 그냥 row/3x3, col/3x3 의 짧은 코드로 바로 알 수 있다는 것.
2. N-Queen 문제의 풀이와의 차이점. 그 문제에서는 우선 퀸을 놓고, 그 다음에 check 를 했지만 여기에서는 check를 하고, 놓을 수 있다면 스도쿠를 그린다. 왜 다른지까지는 솔직하게 아직 이해하지 못했다. 당시의 스도쿠 문제 풀이는 https://velog.io/@anwlro0212/백준-9663-N-Queen-JAVA 에 있다. 그렇기에 퀸을 놓고 체크할 수도 있지만, 체크를 하고 스도쿠를 그려야 할 수도 있다는 생각이 필요하다. 나는 처음에 이문제를 혼자 풀 때 우선 그리고, check 를 했었다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212