[코딩테스트][Java] 백준 2580, 스도쿠

문제

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

2580번: 스도쿠

예를 들어 위와 같은 스도쿠 입력이 주어졌을때 빈칸을 채워서 스도쿠를 완성시키는 문제입니다.

 

접근

빈칸에 들어갈 수 있는 후보 숫자들은 아래와 같은 3가지 과정을 거친다음 추려집니다.

1. 좌표 (y,x)에서 가로 줄에 해당하는 숫자들은 제외
2. 좌표 (y,x)에서 세로 줄에 해당하는 숫자들은 제외
3. 좌표 (y,x)가 속한 3*3영역에서 해당하는 숫자들은 제외

예를 들어 (3,3) 좌표의 빈칸은 다음과 같은 과정을 수행합니다.

1. 리스트 초기화 : [1,2,3,4,5,6,7,8,9]
2. 가로줄 제거하고 남은 리스트 : [5]
3. 세로줄 제거하고 남은 리스트 : [5]
4. 3*3 영역안의 숫자들 제거하고 남은 리스트 : [5]

리스트 안의 남은 숫자는 5밖에 없으므로 빈칸에 5를 저장하고 다음 칸으로 이동합니다. 만약 후보 추출 과정을 거쳐서 리스트의 개수가 2개이상이라면 리스트의 앞쪽에서부터 값을 저장하고 만약 저장한 값을 넣었을때 후에 스도쿠가 실패한다면 다음 후보 숫자를 넣어서 재귀호출합니다. 이러한 과정은 백트래킹(BackTracking) 알고리즘으로 작동합니다.

 

 

좌표 (y,x)가 주어졌을때 3*3 영역의 시작 좌표와 종료 좌표를 탐색하는 방법

int start_y = (y/3)*3;
int start_x = (x/3)*3;
		
int end_y = start_y+2;
int end_x = start_x+2;

 

스도쿠 실패조건

1. 3가지 제거 과정을 거치고 리스트의 개수가 0개
2. 후보 숫자들을 다 넣었봤음에도 빈칸이 0이라면 실패

// 실패조건1
// 가로줄, 세로줄, 영역 숫자들을 제거하고 남은 리스트에
// 후보 숫자가 없는 경우
if(list.size()==0)
{
	return false;
}

// 실패조건2 : 후보 숫자들을 다 넣어봤음에도
// 더이상 후보 숫자들을 넣을 수 없는 경우
if(map[row][col]==0)
{
	return false;
}

 

Java언어 기반 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


public class Main {

	/**
	 * 가로줄 제거
	 */
	private static void removeHorizontal(List<Integer> list, int[][] map, int N, int row)
	{
		for(int i=0; i<N; i++)
		{
			if(map[row][i]==0 || !list.contains(map[row][i]))
			{
				continue;
			}			
			list.remove(Integer.valueOf(map[row][i]));
		}
	}
	
	/**
	 * 세로줄 제거
	 */
	private static void removeVertical(List<Integer> list, int[][] map, int N, int col)
	{
		for(int i=0; i<N; i++)
		{
			if(map[i][col]==0 || !list.contains(map[i][col]))
			{
				continue;
			}			
			list.remove(Integer.valueOf(map[i][col]));
		}
	}
	
	/**
	 * 3*3 영역 제거
	 */
	private static void removeArea(List<Integer> list, int[][] map, int y, int x)
	{
		int start_y = (y/3)*3;
		int start_x = (x/3)*3;
		
		int end_y = start_y+2;
		int end_x = start_x+2;
		
		for(int row=start_y; row<=end_y; row++)
		{
			for(int col=start_x; col<=end_x; col++)
			{
				if(map[row][col]==0 || !list.contains(map[row][col]))
				{
					continue;
				}
				list.remove(Integer.valueOf(map[row][col]));
			}
		}
	}
	
	public static boolean solution(int[][] map, int N, int y, int x)
	{
		for(int row=y; row < N; row++)
		{
			for(int col=x; col < N; col++)
			{
				if(map[row][col]==0)
				{
					List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7,8,9));
					
					// step1 가로줄 제거
					removeHorizontal(list, map, N, row);
				
					// 세로줄에 있는 숫자 제거
					removeVertical(list, map, N, col);
					
					// 3*3 영역에 있는 숫자 제거
					removeArea(list, map, row, col);
					
					// 스도쿠 실패
					if(list.size()==0)
					{
						return false;
					}
					
					// 백트래킹
					for(int candidate : list)
					{
						int temp = map[row][col];
						map[row][col] = candidate;
						if(solution(map, N, row, col+1))
						{
							return true;
						}
						map[row][col] = temp;
					}
					
					// 스도쿠 실패
					if(map[row][col]==0)
					{
						return false;
					}
				}
			}
			x=0;
		}
		return true;
	}
	
	public static void print(int[][] map)
	{
		for(int i=0;i<map.length;i++)
		{
			for(int j=0;j<map[i].length;j++)
			{
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = 9;
		int[][] map = new int[N][N];
		
		for(int i=0;i<N;i++)
		{
			String[] line = br.readLine().split(" ");
			map[i] = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
		}
		
		solution(map, N, 0, 0);
		print(map);
	}
}