백준 2580 스도쿠 자바

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

2580번: 스도쿠

 

nQueen문제를 이해했다면 충분히 풀 수 있는 문제다.

쉽게 풀진 못했고 2가지 케이스 때문에 많은 고생을 했다.

 

접근 아이디어

배열을 입력받을 때 0인 배열의 위치 값을 list에 넣는다. 그 후 백트래킹을 하면서 하나하나 값을 확인한다.

해당 자리에 가능한 숫자 배열을 만들고 그 숫자를 하나하나 넣어가며 백트래킹을 한다.

 

다른 분 코드를 보니 배열을 만들지 않고 숫자를 넣어서 체크하던데 그 방식이 공간 복잡도는 훨씬 줄일 수 있겠다.

 

	static boolean[] getPossibleNum(int y, int x) {
		boolean[] possibleNum = new boolean[10];
		
		//작은 배열에서 넣을 수 있는 숫자 계산
		for (int i = (y/3) * 3; i < (y/3) * 3 + 3 ; i++) {
			for (int j = (x/3) * 3; j < (x/3) * 3 + 3; j++) {
				possibleNum[map[i][j]] = true;
			}
		}
		
		//큰 배열에서 넣을 수 있는 값 계산
		for (int i = 0; i < 9; i++) {
			possibleNum[map[i][x]] = true;
			possibleNum[map[y][i]] = true;
		}
		
		
		//해당자리의 n이 가질 수 있는 값 리스트가 리턴됨
		return possibleNum;
		
		
	}

해당 자리에 2,3,4가 들어간다면 2,3,4 배열만 false다.

 

그리고 1부터 10까지 해당 숫자를 다 넣어보면서 재귀를 수행한다.

for (int i = 1; i < 10; i++) {
			if(!possibleNum[i]) {
				map[p.y][p.x] = i;
				sdoku(n+1);
			}
		}

 

잘 한 부분

해당 자리에 넣을 수 있는 숫자를 계산하는 부분을 어렵지 않게 작성했고. 예제 케이스는 쉽게 통과했다. 

nQueen문제를 이해하고 풀어서 백트래킹 설계를 잘했다.

 

부족한 부분

백트래킹을 수행하고 실패했다면 0으로 만들어줘야 한다. 이 부분을 놓쳐서 많은 시간을 소비했다. 

0으로 만드는 코드를 넣는 곳을 선별하는 것도 쉽지 않았다. 막연히 if(!possibleNum[i[) else {이곳}

 

에다 넣으면 해결되는 줄 알았는데 틀렸다. for문 바깥에 0으로 만드는 코드를 삽입해서 해결했지만 아직 그 차이를 이해하지 못했다.

 

두 번째는 시스템 종료 구문이다. 한 번만 출력해야 하니 한번 출력하고 시스템을 종료해야 한다. 나는 스택에 쌓인 함수를 한 번에 종료할 수 있는 방법이 있는 줄 알고 한참을 고민했는데 그냥 시스템을 종료해야 했다. 조금 황당했고 정답률 이 왜 낮은지 알 수 있었다.

 

세 번째는 공간 복잡도다. 다른 분의 코드보다 조금 빠르지만 공간은 4배나 잡아먹는다. 아마 list를 선언하는 부분과 가능한 숫자를 boolean배열로 받아오는 부분에서 문제가 발생한 것 같다.

또한 문제를 쪼개서 가로, 세로, 작은 네모 이렇게 비교해가며 해결할 수 있었는데 한 번에 모든 숫자를 찾아서 해결하려고 했다. 문제를 쪼개는 습관을 길러야 한다!

 

package backjon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int T;
	static int[][] map;
	static List<Place> list = new ArrayList<>();
	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new int[9][9];
		for (int i = 0; i < 9; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++) {
				int n = Integer.parseInt(st.nextToken());
				map[i][j] = n;
				if(n == 0) list.add(new Place(i, j));
			}
		}
		sdoku(0);
	}
	
	
	private static void sdoku(int n) {
		if(n == list.size()) {
			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);
			return;
		}

		
		Place p = list.get(n);
		boolean[] possibleNum = getPossibleNum(p.y, p.x);
		
		for (int i = 1; i < 10; i++) {
			if(!possibleNum[i]) {
				map[p.y][p.x] = i;
				sdoku(n+1);
			}
		}
		map[p.y][p.x] = 0;
		
	}
	
	static boolean[] getPossibleNum(int y, int x) {
		boolean[] possibleNum = new boolean[10];
		
		//작은 배열에서 넣을 수 있는 숫자 계산
		for (int i = (y/3) * 3; i < (y/3) * 3 + 3 ; i++) {
			for (int j = (x/3) * 3; j < (x/3) * 3 + 3; j++) {
				possibleNum[map[i][j]] = true;
			}
		}
		
		//큰 배열에서 넣을 수 있는 값 계산
		for (int i = 0; i < 9; i++) {
			possibleNum[map[i][x]] = true;
			possibleNum[map[y][i]] = true;
		}
		
		
		//해당자리의 n이 가질 수 있는 값 리스트가 리턴됨
		return possibleNum;
		
		
	}


	static class Place{
		int y, x;

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

}