백준 2580 (스도쿠) java

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

2580번: 스도쿠

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

import static java.lang.System.exit;

/*
 * 백준 1987 알파벳
 * 세로 R , 가로 C
 * 말은 상하좌우 이동 -> bfs 생각 열어두기
 * 새로 이동한 칸의 알파벳은 중복 불가
 * 좌측 상단 (1,1) -> 출발점이 주어진다
 * 말이 최대 몇칸 지날 수 있나? , 출발점 포함 , visit[1][1] = 1
 */
public class Main {
    static int answer = 0;
    static int[][] board = new int[10][10];
    static point[] goal = new point[82];
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i=1;i<=9;i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=9;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j]==0)
                {
                    count++;
                    goal[count] = new point(i,j);
                }
            }
        }
        travel(1);
        bw.flush();
        bw.close();
        br.close();
    }


    static void travel(int num) throws IOException {
        if(num>count)
        {
            if(answer==0) {
                for (int i = 1; i <= 9; i++) {
                    for (int j = 1; j <= 9; j++) {
                        bw.write(board[i][j] + " ");
                    }
                    bw.write("\n");
                }
            }
            answer++;
            return;
        }

        for(int i=1;i<=9;i++)
        {
            if(row(goal[num].x,i)&&col(goal[num].y,i)&&squre(goal[num].x,goal[num].y,i))
            {
                board[goal[num].x][goal[num].y] = i;
                travel(num+1);
                board[goal[num].x][goal[num].y] = 0;
            }
        }


    }

    static boolean row(int x,int num)
    {
        for(int i=1;i<=9;i++)
        {
            if(board[x][i]==num)
                return false;
        }
        return true;
    }
    static boolean col(int x,int num)
    {
        for(int i=1;i<=9;i++)
        {
            if(board[i][x]==num)
                return false;
        }
        return true;
    }

    static boolean squre(int x,int y,int num)
    {
        int ex = x-1;
        int ey = y-1;
        int xl = ex / 3;
        int yl = ey / 3;
        xl = 1 + xl*3;
        yl = 1 + yl*3;

        for(int k=xl;k<xl+3;k++)
        {
            for(int l=yl;l<yl+3;l++)
            {
                if(board[k][l]==num)
                    return false;
            }
        }

        return true;
    }
}
class point
{
    int x;
    int y;

    point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}

비어있는 좌표에 대해 스도쿠의 규칙 ( 행, 열, 3 * 3 배열 )에 대해 만족하는지 확인하여 백트랙킹을 실행한다.

참고로 특정 경우에 대해 답이 가능한 경우의 수가 2개 이상일 수 있다. 그렇기 때문에 해당 경우에 대한 처리를 해 줘야 한다.