백준 2580번 스도쿠 [Java, Kotlin]

: ) YOUNG·2022년 5월 26일
2

알고리즘

목록 보기
138/422
post-thumbnail

백준 2580번
https://www.acmicpc.net/problem/2580

문제



게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.


생각하기


2차원 배열에서 행, 열을 탐색하는 과정 자체가 백트래킹의 대표에제인 N-Queen과 굉장히 유사한 문제였던 것 같다.

N-Queen을 풀어보긴 했지만, 혼자 힘으로 해결한게 아니어서 그런지 이 문제도 몇시간을 고민하고 나서 결국 다른 분들의 코드를 보고 해결 할 수 있었다.

동작

2차원 배열을 스도쿠 형식으로 생성하고 난 후 부터 시작한다.
sdoku메소드를 재귀를 통해 실행해서 배열을 전체 탐색한다.


		// 열이 9일경우 다음 줄로 넘어가기위해 행을 1증가시킴.
		if(y == 9) {
			sdoku(x + 1, 0);
			return;
		}

		// 행이 9에 도달해서 마지막 줄 까지 왔을 때, 종료
		if(x == 9) {
			StringBuilder sb = new StringBuilder();

			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					sb.append(arr[i][j]).append(' ');
				}
				sb.append('\n');
			}
			System.out.println(sb);
			System.exit(0);
		}

위 2가지는 재귀에서 탈출을 하는 2가지 조건인데

if(y == 9) {y가 9일 때, 다음 행으로 넘기기 위한 줄바꿈이 필요하다는 것을 알리기위한 조건문이다.

if(x == 9) {x가 9일 때, 모든 스도쿠배열을 탐색을 마쳤으므로 출력하고 종료하는 조건문이다.


		// 스도쿠배열에서 빈칸인 0을 만났을 때,
		if(arr[x][y] == 0) {
			for(int i=1; i<=N; i++) {
				if(check(x, y, i)) {
					arr[x][y] = i;
					sdoku(x, y + 1);
				}
			}

			arr[x][y] = 0;
			return;
		}

		sdoku(x, y + 1);

해당 부분은 빈칸인 0을 만났을 때 이다.
arr이 0일 때 빈칸을 만나면 check메소드를 실행하게 되는데,
여기서 우리가 스도쿠에서 빈칸에 알맞은 숫자를 채우기 위한 방법은 1~9까지의 숫자를 모두 대입해보는 방식이다.


	static boolean check(int x, int y, int value) {

		for(int i=0; i<N; i++) {
			if(arr[x][i] == value) {
				return false;
			}
  		}

		for(int i=0; i<N; i++) {
			if(arr[i][y] == value) {
				return false;
			}
		}

		int setX = (x/3) * 3;
		int setY = (y/3) * 3;

		for(int i=setX; i<setX + 3; i++) {
			for(int j=setY; j<setY + 3; j++) {
				if(arr[i][j] == value) {
					return false;
				}
			}
		}

		return true;

check함수는 내가 넣으려는 숫자가 스도쿠의 조건에 부합해서 넣을 수 있는 숫자인지를 검사하는 메소드이다.

1~9까지의 숫자를 check의 매개변수인 value에 넣어서 전체 조건을 검사한다.

  • 첫 번째 조건은 if(arr[x][i] == value) { 으로 행에서 이 value와 겹치는 숫자가 있는지 검사한다.
  • 두 번째 조건은 if(arr[i][y] == value) { 열에서 value와 겹치는 숫자가 있는지 검사한다.
  • 세 번째 조건은
int setX = (x/3) * 3; 
int setY = (y/3) * 3;` 

xy의 값을 통해 작은 3x3 배열에서 겹치는 숫자가 있는지 검사하는 것이다.

이 3가지 조건을 모두 통과하면 true를 반환하게 된다.


		// 스도쿠배열에서 빈칸인 0을 만났을 때,
		if(arr[x][y] == 0) {
			for(int i=1; i<=N; i++) {
				if(check(x, y, i)) {
					arr[x][y] = i;
					sdoku(x, y + 1);
				}
			}

			arr[x][y] = 0;
			return;
		}

		sdoku(x, y + 1);

이후 다시 check가 true를 받았을 경우로 돌아오면,
i가 적합한 것을 알게되고 arr[x][y] 의 값을 i로 갱신해주고 다음 열로 넘어가기 위해 sdoku메소드를 재귀 실행한다.



코드



Java

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

public class Main {
	static int N = 9;
	static int arr[][] = new int[N][N];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		sdoku(0, 0);
	} // End of main

	static void sdoku(int x, int y) {

		// 열이 9일경우 다음 줄로 넘어가기위해 행을 1증가시킴.
		if(y == 9) {
			sdoku(x + 1, 0);
			return;
		}

		// 행이 9에 도달해서 마지막 줄 까지 왔을 때, 종료
		if(x == 9) {
			StringBuilder sb = new StringBuilder();

			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					sb.append(arr[i][j]).append(' ');
				}
				sb.append('\n');
			}
			System.out.println(sb);
			System.exit(0);
		}
	

		// 스도쿠배열에서 빈칸인 0을 만났을 때,
		if(arr[x][y] == 0) {
			for(int i=1; i<=N; i++) {
				if(check(x, y, i)) {
					arr[x][y] = i;
					sdoku(x, y + 1);
				}
			}

			arr[x][y] = 0;
			return;
		}

		sdoku(x, y + 1);
	} // End of DFS

	static boolean check(int x, int y, int value) {

		for(int i=0; i<N; i++) {
			if(arr[x][i] == value) {
				return false;
			}
  		}

		for(int i=0; i<N; i++) {
			if(arr[i][y] == value) {
				return false;
			}
		}

		int setX = (x/3) * 3;
		int setY = (y/3) * 3;

		for(int i=setX; i<setX + 3; i++) {
			for(int j=setY; j<setY + 3; j++) {
				if(arr[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	} // End of check

} // End of Main class

Kotlin

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

private val N = 9;
private val arr = Array(N){Array(N){0}}

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )

    for(i in 0 until N) {
        var st = StringTokenizer(br.readLine())
        for(j in 0 until N) {
            arr[i][j] = st.nextToken().toInt()
        }
    }

    sdoku(0, 0)
} // End of main

fun sdoku(x : Int, y : Int) {

    // 열이 9일 경우 다음행으로 넘어감 (줄바꿈)
    if(y == N) {
        sdoku(x + 1, 0);
        return;
    }

    // 행이 9가 됬을 경우, 모든 탐색 완료 종료.
    if(x == N) {
        val sb = StringBuilder();

        for(i in 0 until N) {
            for(j in 0 until N) {
                sb.append(arr[i][j]).append(' ')
            }
            sb.append('\n')
        }
        println(sb)
        System.exit(0);
    }

    // 스도쿠 배열에서 빈칸을 만났을 때,
    if(arr[x][y] == 0) {

        // 1 ~ 9까지 모든 숫자를 대입해보면서 조건에 맞는 숫자를 찾음
        for(i in 1 until 10) {

            // 조건이 true일 경우, 빈칸에 해당 숫자를 넣고
            // 다음 줄로 넘어감.
            if(check(x, y, i)) {
                arr[x][y] = i;
                sdoku(x, y + 1);
            }
        }

        arr[x][y] = 0;
        return;
    }

    sdoku(x, y + 1);
} // End of sdoku

fun check(x : Int , y : Int, value : Int) : Boolean {

    // 열에 value가 있으면, false를 반환
    for(i in 0 until N) {
        if(arr[x][i] == value) {
            return false;
        }
    }

    // 행도 검사해서 value가 있으면 false 처리
    for(i in 0 until N) {
        if(arr[i][y] == value) {
            return false;
        }
    }


    // x, y를 기준으로 3*3 배열의 시작점을 찾음
    val setX = (x / 3) * 3;
    val setY = (y / 3) * 3;

    // 3*3 배열에서 value와 겹치는 숫자가 있는지 검사
    for(i in setX until setX+3) {
        for(j in setY until setY+3) {
            if(arr[i][j] == value) {
                return false;
            }
        }
    }

    // 모든 조건 통과 하면 true를 반환
    return true;
} // End of check

0개의 댓글