[알고리즘] 백준 2580 스도쿠 -백트랙킹(dfs)- 자바, 코틀린

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

 

 

백준 백트랙킹 단계별풀기의 2580 스도쿠 문제를 풀어봤습니다.

 

1. 처음 입력받는 값을 map에 세팅시 0(빈칸)인 값을 리스트에 넣어줍니다.

 

2. 첫줄(depth)부터 dfs를 채워주고 조건은 빈값을 모두 채운 경우 끝내줍니다.

 

3. 빈값의 좌표를 불러오고 해당 좌표에 1~9 모두 넣어서 되는값인지 check 해줍니다.

 

4. check를 통과하면 해당 빈 좌표에 해당 값이 들어가고 dfs를 이어서 돌려줍니다.

 

 

주석으로 풀이를 정리해놨습니다.

 

[Java]

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int[][] map = new int[9][9];
    static LinkedList<Node> list = new LinkedList();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 0) {
                    list.add(new Node(i, j));
                }
            }
        }
        dfs(0);
    }

    static void dfs(int depth) {
        if (depth == 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);
        }
        Node node = list.get(depth);
        int x = node.x;
        int y = node.y;
        for (int i = 1; i <= 9; i++) { //빈칸인 map[x][y]에 1~9 값 되는지 check
            if (check(x, y, i)) {
                map[x][y] = i; //되는 숫자면 넣고 이어서 탐색
                dfs(depth + 1);
                map[x][y] = 0;
            }
        }
    }

    static boolean check(int x, int y, int num) {
        if (map[x][y] != 0) { // 빈칸 아니면 false
            return false;
        }
        for (int i = 0; i < 9; i++) { //가로,세로줄 중복검사
            if (map[i][y] == num || map[x][i] == num) {
                return false;
            }
        }
        int x2 = (x / 3) * 3;
        int y2 = (y / 3) * 3;
        for (int i = x2; i < x2 + 3; i++) { //3x3 중복체크
            for (int j = y2; j < y2 + 3; j++) {
                if (map[i][j] == num) {
                    return false;
                }
            }
        }
        return true;

    }


    static class Node {
        int x; //행
        int y; //열

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

 

 

[Kotlin]

import java.util.*

internal var map = Array(9) { IntArray(9) }
internal var list: LinkedList<Node> = LinkedList()

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    for (i in 0..8) {
        for (j in 0..8) {
            map[i][j] = sc.nextInt()
            if (map[i][j] == 0) {
                list.add(Node(i, j))
            }
        }
    }
    dfs(0)
}

internal fun dfs(depth: Int) {
    if (depth == list.size) {
        for (i in 0..8) {
            for (j in 0..8) {
                print(map[i][j].toString() + " ")
            }
            println()
        }
        System.exit(0)
    }
    val node = list[depth]
    val x = node.x
    val y = node.y
    for (i in 1..9) { //빈칸인 map[x][y]에 1~9 값 되는지 check
        if (check(x, y, i)) {
            map[x][y] = i //되는 숫자면 넣고 이어서 탐색
            dfs(depth + 1)
            map[x][y] = 0
        }
    }
}

internal fun check(x: Int, y: Int, num: Int): Boolean {
    if (map[x][y] != 0) { // 빈칸 아니면 false
        return false
    }
    for (i in 0..8) { //가로,세로줄 중복검사
        if (map[i][y] == num || map[x][i] == num) {
            return false
        }
    }
    val x2 = x / 3 * 3
    val y2 = y / 3 * 3
    for (i in x2 until x2 + 3) { //3x3 중복체크
        for (j in y2 until y2 + 3) {
            if (map[i][j] == num) {
                return false
            }
        }
    }
    return true

}


data class Node(var x: Int, var y: Int)

github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%202580%20%EC%8A%A4%EB%8F%84%EC%BF%A0%20-%EB%B0%B1%ED%8A%B8%EB%9E%99%ED%82%B9-

mtjin/algorithm_practice

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!