백준 2580 - 스도쿠 (백트래킹, JAVA)

자력구현

 

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

2580번: 스도쿠

 

이거 시간 대충 580인데 300대로 줄일 수 있음

메모리도 10만에 가까운데 2만으로 줄일 수있음

 

병신코드임

방법론
1. 해당 포인트를 담는 자료구조 pair 제작
2. 입력 받을 때, 0인 부분 인덱스 체크해서, 포인트 어레이리스트에 집어넣음
3. 포인트 어레이리스트 크기를 최종 뎁스로 선정
4. 각 뎁스마다, 즉, 각 0인 포인트마다 가능한 경우의 수를 담는 인접리스트 checked 제작
5. 해당 포인트에서 가능한 경우의 수를 찾는 caseCheck 함수 제작 (행, 열, 3x3 크기 검사 함수임)
6. 백트래킹 함수 실행 뎁스는 0부터 시작
7. 포인트 어레이리스트의 인덱스와 checked 인접리스트의 인덱스가 1씩 차이나는거 유의
8. 해당 뎁스의 포인트값을 a b 에 할당, 그 a b 를 가지고 caseCheck 함수 실행
9. 그러면 인접리스트에 해당 뎁스에 관한 경우의 수가 담겨 있다. 그걸로 포문을 돌린다.
10. 최종뎁스에 도달하면 return

만드는데 시간잡아먹었던 부분
1. 백트래킹 초기화를 안함, 백트래킹이 발동될 때, 해당 뎁스의 해당 포인트 값을 0으로, 즉, A[a][b] =0, 그리고 해당 뎁스의 인접리스트를 초기화해야함
2. 최종 뎁스 도달시 모든 깊이의 함수에 대해서 끝을 내야하는데, 포문이 돌아가는 상황이면, 포문 후 따로 리턴 설정이 필요함
이거 안하면, 해당 뎁스의 포인트 값이 0으로 초기화 되어버려서 출력 값이 이상하게 나옴

 

방법론 핵심요약

- 스도쿠 판의 0인 부분을 깊이로 설정, 해당 0에서 가능한 경우의 수에 대해 포문을 돌리면서 백트래킹을 돌린다.

 

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

public class Main
{
	static int[][] A = new int[10][10];
	static ArrayList<pair> Point = new ArrayList<>();
	static ArrayList<ArrayList<Integer>> checked = new ArrayList<>();
	static int finalDepth;
	static boolean done = false;
	
	public static class pair
	{
		int x,y;
		
		pair () {}
		
		pair (int x, int y) { this.x = x; this.y = y; }
	}
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		for (int i=1; i<=9; i++)
		{
			st = new StringTokenizer(input.readLine());
			
			for (int j=1; j<=9; j++)
			{
				int temp = Integer.parseInt(st.nextToken());
				
				A[i][j] = temp;
				
				if ( temp == 0 )
					Point.add(new pair(i,j));
			}
		}
		
		finalDepth = Point.size();
		
		for (int i=0; i<=finalDepth; i++)
			checked.add(new ArrayList<>());
		
		backTracking (0);
		
		for (int i=1; i<=9; i++)
		{
			for (int j=1; j<=9; j++)
			{
				output.write(A[i][j] + " ");
			}
			output.write("\n");
		}
		output.close();
		
	}
	
	public static void backTracking (int depth)
	{
		if ( depth == finalDepth || done == true )
		{
			done = true;	
			return;
		}
		
		int a = Point.get(depth).x;
		int b = Point.get(depth).y;
		
		depth++;

		caseCheck (a, b, depth);
		
		int size = checked.get(depth).size();
		
		for (int i=0; i<size; i++)
		{	
			if (done == true)
				break;
			
			A[a][b] = checked.get(depth).get(i);
			
			backTracking (depth);
		}
		
		if (done == true)
			return;
		
		checked.get(depth).clear();
		A[a][b] = 0;
	}
	
	public static void caseCheck (int a, int b, int depth)
	{
		boolean[] temp = new boolean[10];
		
		for (int i=1; i<=9; i++)
		{
			if ( A[a][i] != 0)
				temp[ A[a][i] ] = true;
			
			if ( A[i][b] != 0)
				temp[ A[i][b] ] = true;
		}
		
		int n, m;
		
		if ( a % 3 == 0)
			n = a-2;
		else if ( a % 3 == 1)
			n = a;
		else
			n = a-1;
			
		if ( b % 3 == 0)
			m = b-2;
		else if ( b % 3 == 1)
			m = b;
		else
			m = b-1;
			
		for (int i=n; i<=n+2; i++)
		{
			for (int j=m; j<=m+2; j++)
			{
				if ( A[i][j] != 0)
					temp[ A[i][j] ] = true;
			}
		}
		
		for (int i=1; i<=9; i++)
		{
			if (temp[i] == false)
				checked.get(depth).add(i);
		}
	}
}