고도고도
🍎🍏
고도고도
전체 방문자
8,030
오늘
0
어제
31
  • 분류 전체보기 (151) N
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (44) N
      • TIL (16)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Error (4) N
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (51)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (8)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

인기 글

  • [TIL] 22.03.13
    2022.03.13
    [TIL] 22.03.13
  • [문자열 / Kotlin] 2020 KAKAO⋯
    2022.03.11
    [문자열 / Kotlin] 2020 KAKAO⋯
  • [TIL] 22.03.20
    2022.03.20
    [TIL] 22.03.20
  • [퍼듀 일기] 적응 완료
    2022.03.05
    [퍼듀 일기] 적응 완료
  • [구현 / Kotlin] 2022 SK ICT F⋯
    2022.03.12
    [구현 / Kotlin] 2022 SK ICT F⋯

최근 글

  • [Error / Gradle] mockup1/andr⋯
    2022.08.13
    [Error / Gradle] mockup1/andr⋯
  • [NCSOFT] 2022 NC Summer Inter⋯
    2022.08.10
    [NCSOFT] 2022 NC Summer Inter⋯
  • [Flutter] ModalBottomSheet가⋯
    2022.08.09
    [Flutter] ModalBottomSheet가⋯
  • [Error / Gradle] The current⋯
    2022.08.09
    [Error / Gradle] The current⋯
  • [Flutter / Dart] What is Equa⋯
    2022.08.06
    [Flutter / Dart] What is Equa⋯

최근 댓글

  • NC......가슴이...웅장해집니다⋯
    이상한핑구 🐧
  • 고도고도님 멋져요!
    mjj
  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
hELLO · Designed By 정상우.
고도고도

🍎🍏

[백트래킹 / Kotlin] BOJ 2580 - 스도쿠
✍️ 코테 준비/Back Tracking

[백트래킹 / Kotlin] BOJ 2580 - 스도쿠

2022. 3. 30. 10:50

문제

풀이 언어

Kotlin

코드

import java.util.*
import kotlin.system.exitProcess

lateinit var board: Array<Array<Int>>

fun main() = with(Scanner(System.`in`)) {
    board = Array(9) { Array(9) { 0 } }

    // 주어진 배열을 입력받음
    for (i in 0 until 9) {
        for (j in 0 until 9) {
            board[i][j] = nextInt()
        }
    }

    // (0, 0) 부터 시작
    sudoku(0, 0)
}


fun check(row: Int, col: Int, value: Int): Boolean {
    // 1. 같은 행, 다른 열에 같은 값이 존재하는지 확인
    for (i in 0 until 9) {
        if (board[row][i] == value) return false
    }

    // 2. 다른 행, 같은 열에 같은 값이 존재하는지 확인
    for (i in 0 until 9) {
        if (board[i][col] == value) return false
    }

    // 3. (3x3) 블럭 내부에 같은 값이 존재하는지 확인
    // 현재 위치가 어느 위치의 (3x3) 블럭에 있는지를 우선 확인
    val r_index  = row / 3 * 3
    val c_index = col / 3 * 3

    for (i in 0 until 3) {
        for (j in 0 until 3) {
            if (board[r_index + i][c_index + j] == value) return false
        }
    }

    return true
}

fun sudoku(row: Int, col: Int) {
    if (col == 9) {
        sudoku(row + 1, 0)
        return
    }

    if (row == 9) {
        val stringBuilder = StringBuilder()

        board.map {
            it.iterator().forEach { e ->
                stringBuilder.append(e).append(' ')
            }
            stringBuilder.append('\n')
        }

        println(stringBuilder)
        // 시스템 종료
        exitProcess(0)
    }

    if (board[row][col] == 0) {
        for (i in 1..9) {
            if (check(row, col, i)) {
                board[row][col] = i
                sudoku(row, col + 1)
            }
        }
        board[row][col] = 0
        return;
    }

    sudoku(row, col + 1)
}

풀이 방법

스도쿠는 아래와 같은 규칙을 갖는다.

  1. 같은 행에는 1 ~ 9 가 중복 없이 존재한다.
  2. 같은 열에는 1 ~ 9 가 중복 없이 존재한다.
  3. 같은 블럭 (3x3) 에는 1 ~ 9 가 중복 없이 존재한다.

위 규칙에 따라 백트래킹 으로 구현한다.

 

하지만 중요한 것 이 한 가지 있다. 현재 좌측 상단부터 값을 넣어주는데 해당 위치의 값이 0 인 경우에 중복 여부를 판별하고 값을 집어넣지만 진행 과정에서 이 값이 잘못된 값이 될 수 있다. 가령 7이 들어가야 하는 자리에 위 조건을 만족한 다른 숫자가 들어가게 되면 이후의 모든 DFS 는 잘못된 값이 채워지게 된다. 따라서 해당 지점을 1 ~ 9 로 바꿔주되 이를 다시 0 으로 변경하여 모든 경우에 대해 탐색할 수 있도록 만들어줘야 한다. (처음 문제 풀 때 이 부분을 놓쳐서 값이 이상하게 출력되었다.)

 

1. 주어진 입력 값을 배열에 저장한다.

fun main() = with(Scanner(System.`in`)) {
    board = Array(9) { Array(9) { 0 } }

    // 주어진 배열을 입력받음
    for (i in 0 until 9) {
        for (j in 0 until 9) {
            board[i][j] = nextInt()
        }
    }

    // (0, 0) 부터 시작
    sudoku(0, 0)
}

 

2. (0, 0) -> (0, 1) ... 순으로 채워나간다. 이 때 해당 위치의 값이 0인 경우 어떤 값을 채워줄 지에 대해 판별한다.

    if (board[row][col] == 0) {
        for (i in 1..9) {
            if (check(row, col, i)) {
                board[row][col] = i
                sudoku(row, col + 1)
            }
        }
        board[row][col] = 0
        return;
    }

 

3. 스도쿠 규칙에 맞게 중복 값 여부를 판별한다.

fun check(row: Int, col: Int, value: Int): Boolean {
    // 1. 같은 행, 다른 열에 같은 값이 존재하는지 확인
    for (i in 0 until 9) {
        if (board[row][i] == value) return false
    }

    // 2. 다른 행, 같은 열에 같은 값이 존재하는지 확인
    for (i in 0 until 9) {
        if (board[i][col] == value) return false
    }

    // 3. (3x3) 블럭 내부에 같은 값이 존재하는지 확인
    // 현재 위치가 어느 위치의 (3x3) 블럭에 있는지를 우선 확인
    val r_index  = row / 3 * 3
    val c_index = col / 3 * 3

    for (i in 0 until 3) {
        for (j in 0 until 3) {
            if (board[r_index + i][c_index + j] == value) return false
        }
    }

    return true
}

결과

참고 블로그

2580번 : 스도쿠 - JAVA

저작자표시비영리변경금지

'✍️ 코테 준비 > Back Tracking' 카테고리의 다른 글

[백트래킹 / Kotlin] BOJ 1759 - 암호 만들기  (0) 2022.04.10
[백트래킹 / Kotlin] BOJ 1987 - 알파벳  (0) 2022.04.10
[백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기  (0) 2022.03.31
[백트래킹 / Kotlin] BOJ 2580 - 스도쿠  (0) 2022.03.30
[백트래킹 / Kotlin] BOJ 9663 - N Queen  (0) 2022.03.29
[백트래킹 / Kotlin] BOJ 15649 ~ 15652 - N과 M (1 ~ 4)  (0) 2022.03.28
    '✍️ 코테 준비/Back Tracking' 카테고리의 다른 글
    • [백트래킹 / Kotlin] BOJ 1987 - 알파벳
    • [백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기
    • [백트래킹 / Kotlin] BOJ 9663 - N Queen
    • [백트래킹 / Kotlin] BOJ 15649 ~ 15652 - N과 M (1 ~ 4)
    고도고도
    고도고도
    좋아하는 것을 하자\n 스위프트 찍먹중\n 광고 없는 블로그
    댓글쓰기
    다음 글
    [백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기
    이전 글
    [백트래킹 / Kotlin] BOJ 9663 - N Queen
    • 이전
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 다음