[백준 2580번/JAVA] 스도쿠 (문제 풀이, 코드)

스도쿠

[문제]

위 그림과 같은 입력의 스도쿠를 스도쿠 규칙대로 0인 자리들을 채워넣으면 된다.

 

[풀이]

2661번 문제인 좋은 수열과 마찬가지로 해당 문제도 백트래킹 알고리즘을 사용한다.

백트래킹 알고리즘? 어떤 노드가 유망하지 않으면 해당 노드의 부모로 되돌아간 후 다른 노드를 탐색

 

[내 코드 알고리즘]

1. 0의 위치가 저장되어 있는 zeroq[i]에 넣을 수 있는 수를 탐색 FindPossible(i) 해당 수들을 모두 stack에 push()한다.
2. stack.pop() 을 해서 sdoku 판에 넣는다.
3. i = zeroq의 현재 index+1
4. i == zeroq.size() 면 stop. 아니라면 1번으로 돌아간다.
   • 이때 i++이 아니라 zeroq.size()를 한 이유
   • FindPossible을 하여 가능한 수가 없을 때, push없이 pop을 하게 된다. 만약 i++을 했다면 다음 FindPossible을 할때 한 칸을 건너뛰게 되기 때문.

[코드]

package j;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

class zeropos{
	int x,y,ans,i;
	zeropos(int x,int y){
		this.x =x; this.y =y;
	}
	zeropos(int i, int x,int y){
		this.i = i; this.x = x; this.y = y;
	}
	zeropos(int i,int x, int y, int ans){
		this.i=i; this.x=x; this.y=y; this.ans=ans;
	}
}
public class sdoku_2580 {
	static int N = 9;
	static int[][] sdoku;
	static ArrayList<zeropos> zeroq;
	static Stack<zeropos> stack;
	static boolean[] isExist;
	static zeropos[][] Square;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		sdoku = new int[N][N]; zeroq = new ArrayList<>();
		stack = new Stack<>(); isExist = new boolean[N+1];
		Square = new zeropos[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++){
				sdoku[i][j] = Integer.parseInt(st.nextToken());
				if(sdoku[i][j] == 0) zeroq.add(new zeropos(zeroq.size(),i,j));
				}
		}
		makeSquare(); int i = 0;
		while(true) {
			make_zero(i);
			FindPossible(i);
			zeropos zero = stack.pop();
			sdoku[zero.x][zero.y]=zero.ans;
			//System.out.println(zero.x+","+zero.y+"="+zero.ans);
			i = zero.i+1;
			if(i==zeroq.size()) break;
			//print_sdoku(); System.out.println();
		}
		print_sdoku(); 
	}
}

[후기]

본의 아니게 저번 문제와 이번 문제 둘 다 백트래킹을 연습할 수 있었다.

코드의 알고리즘 자체는 정석적인 것 같은데 내 코드의 경우 조금 비효율적인 메모리 사용을 한 것 같다. 이번주 알고리즘 스터디때 다른사람들의 코드를 참고해봐야겠다.

 

[문제점]

이 문제를 풀면서, stack에 넣을때 객체 자체를 바로 넣었었는데(값은 변경해가면서) 그러니까 마지막에 변경한 값으로 모두 바뀌어버렸다.대체 왜 그렇게 됐는지 생각해보니, 객체가 같은 주소를 가리키고 있었고, 해당 주소의 값을 변경하니까 그 주소를 가리키는 애들이 모두 바뀐 것 같다.이 문제는 new로 객체를 만들어주면서 해결했다.처음 코드를 어떻게 짤지 고민할때, 제일 먼저 무조건 답일 수 밖에 없는 애들을 체킹했었는데(9칸 중 숫자 하나 빼고 모두 나온 경우) 이것을 하니 불필요한 코드? 중복되는 코드? 어쨌든 예외로 코드를 더 둬야해서 그냥 한 번에 할 수 있는 방식으로 바꿨다.

 

GitHub에 해당 코드의 full ver가 업로드되어 있습니다.

github.com/MOBUMIN/BJalgorithm/blob/master/02000-2999/sdoku_2580.java

MOBUMIN/BJalgorithm