백준(2239번) - 스도쿠 (Java) (구현)

문제를 계속 시도했지만, 끝내 통과하지 못한 문제이다.

<실패한 코드>

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

public class Main
{
	static int[][] map = new int[9][9];
	static boolean[] use;
	static ArrayList<int[]> list;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		list = new ArrayList<>();
		
		for(int i = 0 ; i < 9 ; i++)
		{
			String str = br.readLine();
			for(int j = 0 ; j < 9 ; j++)
			{
				map[i][j] = str.charAt(j) - '0';
				if(map[i][j] == 0) list.add(new int[]{i,j});
			}
		}
		
		sudoku(0);
		
	}
	public static void sudoku(int cnt)
	{
		if(list.size() == cnt)
		{
			print();
			return;
		}

		int x = list.get(cnt)[0];
		int y = list.get(cnt)[1];
			
		use = new boolean[10];
		
		int div_x = (x/3)*3;
		int div_y = (y/3)*3;
		
		for(int i = 0 ; i < 9 ; i++)	//십자 형태의 숫자 파악
		{
			if(map[i][y] > 0) use[map[i][y]] = true;
			if(map[x][i] > 0) use[map[x][i]] = true;
		}
		
		for(int i = div_x ; i < (div_x)+3 ; i++)	//자신이 속한 3x3블럭의 숫자 파악
		{
			for(int j = div_y ; j < (div_y)+3 ; j++)
			{
				if(map[i][j] > 0) use[map[i][j]] = true;
			}
		}
		
		for(int i = 1 ; i < 10 ; i++)
		{
			if(!use[i])
			{
				map[x][y] = i;
				sudoku(cnt+1);
				map[x][y] = 0;
			}
		}
	}
	public static void print()
	{
		for(int i = 0 ; i < 9 ; i++)
		{
			for(int j = 0 ; j < 9 ; j++)
			{
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
}

 계속 도전을 하다가 구글링을 했는데 코드가 동일한 사람이 있었다. 나는 왜 통과가 안 되는지 이해가 안 돼 cnt마다 스도쿠를 뽑아 봤는데 중간에 2행 3열쯤에 숫자를 채워 넣을 수가 없어서 멈춰버린다. 이런 경우엔 백트래킹으로 푼다면 다시 전에 단계로 돌아가 다시 가능한 경우로 돌아 완성해야 하는 걸로 알고 있는데 그게 안된다.

 

계속 잡고 있기엔 무리가 있어서 chatGPT를 이용했는데 

<GPT 코드>

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

public class Main {
    static int[][] map = new int[9][9];
    static boolean[][] rowUsed = new boolean[9][10];
    static boolean[][] colUsed = new boolean[9][10];
    static boolean[][] boxUsed = new boolean[9][10];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 받기
        for (int i = 0; i < 9; i++) {
            String str = br.readLine();
            for (int j = 0; j < 9; j++) {
                map[i][j] = str.charAt(j) - '0';
                if (map[i][j] != 0) {
                    rowUsed[i][map[i][j]] = true;
                    colUsed[j][map[i][j]] = true;
                    boxUsed[(i / 3) * 3 + (j / 3)][map[i][j]] = true;
                }
            }
        }

        sudoku(0);

        br.close();
    }

    public static void sudoku(int cnt) {
        if (cnt == 81) {
            // 출력하기
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(map[i][j]);
                }
                System.out.println();
            }
            System.exit(0);
        }

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

        if (map[x][y] == 0) {
            for (int num = 1; num <= 9; num++) {
                if (!rowUsed[x][num] && !colUsed[y][num] && !boxUsed[(x / 3) * 3 + (y / 3)][num]) {
                    rowUsed[x][num] = true;
                    colUsed[y][num] = true;
                    boxUsed[(x / 3) * 3 + (y / 3)][num] = true;
                    map[x][y] = num;
                    sudoku(cnt + 1);
                    map[x][y] = 0;
                    rowUsed[x][num] = false;
                    colUsed[y][num] = false;
                    boxUsed[(x / 3) * 3 + (y / 3)][num] = false;
                }
            }
        } else {
            sudoku(cnt + 1);
        }
    }
}

 GPT의 설명으로는 사용 숫자를 use하나로 파악할 게 아니라 열, 행, 3x3마다 파악을 해주는 것이 키포인트라는 것 같다.

<문제>

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