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

1. 소요시간 : 17분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 구현, 백트래킹
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
   => 맞을지도 ...? 2239는 처음 풀지만 사실 2580 문제와 완전히 동일하다.
7. 문제 링크 : https://www.acmicpc.net/problem/2239
8. 푼 날짜 : 2023.03.28

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

백트래킹을 사용했다.

2. 사고과정

백준 2580 : https://www.acmicpc.net/problem/2580
문제와 99% 동일하다. 딱 하나 다른 건 거기서는 정답이 여러개일 경우 아무거나 출력하면 됐지만 여기서는 사전 순으로 가장 앞서는 것을 출력한다.
사실 map을 1~9로 차례대로 보고 가지치기한다면 동일한 결과를 얻는다.
그러므로 한 번 푼 문제를 다시 푸는 거라고도 할 수 있겠다.
2주 전쯤 풀었었던 것 같은데 당시에는 문제를 풀지 못해서 다른 사람의 풀이를 참고했었다.

3. 풀이과정

1. map에서 0인 위치를 ArrayList 에 저장.
2. 그리고 이제 0인 위치를 차례대로 check 함.
3. check 메소드는 나와 동일한 세로열, 가로열, 또 내가 속한
   3 x 3 의 위치에서 1~9까지의 숫자를 넣을 수 있나 없나 확인하는 것임. 넣을 수 있다면 넣고, 다음 0인 위치를 찾아감.
4. depth가 ArrayList의 size가 됐다면 0이었던 모든 스도쿠 map을 1~9중 하나로 채운 것임. 그렇게 됐다면 스도쿠 맵을 출력

4. 소스코드

import java.util.*;
import java.io.*;
public class Main {
	static int map[][]=new int[9][9];
	static ArrayList<Integer[]> list=new ArrayList<>();
	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++) {
			String line[]=br.readLine().split("");
			for(int j=0;j<map.length;j++) {
				map[i][j]=Integer.parseInt(line[j]);
				if(map[i][j]==0) 
					list.add(new Integer[] {i,j});
			}
		}
	
	

		backtracking(0);

	}
	public static void backtracking(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);
		}
		
		Integer temp[]=list.get(depth);
		int y=temp[0];
		int x=temp[1];
		
		for(int i=1;i<=9;i++) {
			if(check(y,x,i)) {
				map[y][x]=i;
				backtracking(depth+1);
				map[y][x]=0;
			}
		}
		
		
		
	}
	public static boolean check(int y,int x,int value) {
		
		for(int i=0;i<map.length;i++) {
			if(map[y][i]==value) return false;
			if(map[i][x]==value) return false;
		}
		
		int standardY=y/3*3;
		int standardX=x/3*3;
		
		for(int i=standardY;i<standardY+3;i++) {
			for(int j=standardX;j<standardX+3;j++) {
				if(map[i][j]==value) return false;
			}
		}
		
		
		return true;
	}

}

5. 결과

good!

6. 회고

계속 새로운 문제를 푸는 것도 좋지만 이전에 한 번 실패했던 문제를 1~2주 뒤 다시 풀어보는 것도 좋은 것 같다.

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