고도고도
🍎🍏
고도고도
전체 방문자
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) N
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (8) N

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

인기 글

  • [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 15649 ~ 15652 - N과 M (1 ~ 4)
✍️ 코테 준비/Back Tracking

[백트래킹 / Kotlin] BOJ 15649 ~ 15652 - N과 M (1 ~ 4)

2022. 3. 28. 16:25

N과 M (1)

문제

풀이 언어

Kotlin

코드

import java.util.*

lateinit var visit: Array<Int>
lateinit var input: Array<Int>
var n: Int = 0
var m: Int = 0

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    visit = Array(n + 1) { 0 }
    input = Array(n + 1) { 0 }

    dfs(0)
}

fun dfs(depth: Int) {
    if (depth == m) {
        for (i in 0 until m) {
            print("${input[i]} ")
        }
        println()
        return
    }

    for (i in 0 until n) {
        if (visit[i] == 0) {
            visit[i] = 1

            input[depth] = i + 1
            dfs(depth + 1)

            visit[i] = 0
        }
    }
    return
}

풀이 방법

이 문제는 백트래킹 을 활용하는 문제이다. 백트래킹은 완전 탐색 기법 중에 하나로 DFS (Depth First Search) 에서 가능성이 없는 경우의 수는 배제하여(가지치기) 탐색 속도를 향상시키는 방법이다.

 

우선 입력으로 주어진 n 과 m 에 대해 알아보자. n은 탐색이 진행되는 첫 번째 숫자, m은 탐색 깊이 를 의미한다. 이미 방문한 지점은 Pass 하고 방문하지 않은 지점일 때 더 높은 Depth 에서 탐색을 진행한다. 이 때 m 과 같은 depth 에 진입한 경우 input 에 저장된 결과를 출력한다.

 

가령 4, 4 가 주어졌다고 가정하면 아래와 같이 탐색을 진행한다.

 

1
11(pass)
12
122(pass)
123
1233(pass)
1234
...

결과


N과 M (2)

문제

풀이 언어

Kotiln

코드

import java.util.*

lateinit var visit: Array<Int>
lateinit var input: Array<Int>
var n: Int = 0
var m: Int = 0

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    visit = Array(n + 1) { 0 }
    input = Array(n + 1) { 0 }

    dfs(0, 0)
}

fun dfs(depth: Int, before : Int) {
    if (depth == m) {
        for (i in 0 until m) {
            print("${input[i]} ")
        }
        println()
        return
    }

    for (i in 0 until n) {
        if (visit[i] == 0 && before < i + 1) {
            visit[i] = 1

            input[depth] = i + 1

            dfs(depth + 1, i + 1)

            visit[i] = 0
        }
    }
    return
}

풀이 방법

이전 문제와 동일하지만 한 가지 조건이 추가되었다. 수열이 오름차순 이어야 한다. 이전에 방문한 지점과 현재 방문한 지점을 비교해서 현재 방문한 지점이 더 큰 경우에만 더 높은 Depth 에서 탐색을 진행하도록 한다.

결과


N과 M (3)

문제

풀이 언어

kotlin

코드

import java.util.*

lateinit var visit: Array<Int>
lateinit var input: Array<Int>
var n: Int = 0
var m: Int = 0
var stringBuilder = StringBuilder()

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    visit = Array(n + 1) { 0 }
    input = Array(n + 1) { 0 }

    dfs(0)
    println(stringBuilder)
}

fun dfs(depth: Int) {
    if (depth == m) {
        for (i in 0 until m) {
            stringBuilder.append(input[i]).append(" ")
        }
        stringBuilder.append("\n")
        return
    }

    for (i in 0 until n) {
        input[depth] = i + 1
        dfs(depth + 1)
    }
    return
}

풀이 방법

이전 두 문제와 다르게 이번엔 중복 을 허용 한다. 경우의 수가 훨씬 커졌다. 그래서 단순히 print 를 사용하면 시간 초과 가 발생한다. 출력에 대한 시간을 줄이고자 StringBuilder 를 사용했다.

결과

StringBuilder를 사용하지 않으면 시간 초과가 발생한다.


N과 M (4)

문제

풀이 언어

Kotlin

코드

import java.util.*

lateinit var visit: Array<Int>
lateinit var input: Array<Int>
var n: Int = 0
var m: Int = 0
var stringBuilder = StringBuilder()

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    visit = Array(n + 1) { 0 }
    input = Array(n + 1) { 0 }

    dfs(0, 0)
    println(stringBuilder)
}

fun dfs(depth: Int, before : Int) {
    if (depth == m) {
        for (i in 0 until m) {
            stringBuilder.append(input[i]).append(" ")
        }
        stringBuilder.append("\n")
        return
    }

    for (i in 0 until n) {
        if (before > i + 1) continue
        input[depth] = i + 1
        dfs(depth + 1, i + 1)
    }
    return
}

풀이 방법

이번엔 중복 과 오름차순 을 모두 고려해야 하는 문제이다. 역시 StringBuilder 를 사용해서 출력 시간을 줄인다.

결과

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

'✍️ 코테 준비 > 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 2580 - 스도쿠
    • [백트래킹 / Kotlin] BOJ 9663 - N Queen
    고도고도
    고도고도
    좋아하는 것을 하자\n 스위프트 찍먹중\n 광고 없는 블로그
    댓글쓰기
    다음 글
    [백트래킹 / Kotlin] BOJ 9663 - N Queen
    • 이전
    • 1
    • ···
    • 3
    • 4
    • 5
    • 6
    • 7
    • 다음