고도고도
🍎🍏
고도고도
전체 방문자
13,424
오늘
31
어제
64
  • 분류 전체보기 (170)
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (61)
      • iOS (28)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • 오늘의 삽질 (7)
      • 에러와의 동침 (1)
    • ✏️ 알고리즘 (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)
    • ⛹️ 라이프 (53)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (10)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

공지사항

인기 글

  • [NCSOFT] 2022 엔씨소프트 썸머 인턴 후기 - 1⋯
    2022.08.10
    [NCSOFT] 2022 엔씨소프트 썸머 인턴 후기 - 1⋯
  • [Flutter] SingleChildScrollView,⋯
    2021.08.18
    [Flutter] SingleChildScrollView,⋯
  • [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
    2022.12.20
    [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
  • [Android] 백그라운드에서 소켓 통신으로 이벤트 수신⋯
    2022.06.08
    [Android] 백그라운드에서 소켓 통신으로 이벤트 수신⋯
  • [iOS / SwiftUI] OnAppear, OnDisa⋯
    2022.12.01
    [iOS / SwiftUI] OnAppear, OnDisa⋯

최근 댓글

  • https://developer.apple.com/docu⋯
    고도고도
  • 게시글 잘 보았습니다. 혹시 주소에서 구를 가지고 오시는⋯
    나그네
  • 혹시 댓글이 안보이는데 .. y2e010924@naver.⋯
    eun
  • 글 솜씨가 뛰어나시네요! 좋은 글 잘 보고 갑니다 다음에도⋯
    alpha-traveler
  • NC......가슴이...웅장해집니다.......🤯
    이상한핑구 🐧

최근 글

  • [Architecture] MVVM + Clean Arch⋯
    2023.01.07
    [Architecture] MVVM + Clean Arch⋯
  • [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
    2022.12.20
    [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
  • [iOS / SwiftUI] OnAppear, OnDisa⋯
    2022.12.01
    [iOS / SwiftUI] OnAppear, OnDisa⋯
  • [에러와의 동침] 22년 11월 4주차
    2022.11.28
    [에러와의 동침] 22년 11월 4주차
  • [iOS / SwiftUI] 스크롤, 무한으로 즐겨요~ (⋯
    2022.11.28
    [iOS / SwiftUI] 스크롤, 무한으로 즐겨요~ (⋯

티스토리

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 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)
    고도고도
    고도고도
    iOS 꿀잼
    댓글쓰기
    [백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기
    다음 글
    [백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기
    [백트래킹 / Kotlin] BOJ 9663 - N Queen
    이전 글
    [백트래킹 / Kotlin] BOJ 9663 - N Queen

    티스토리툴바