[Kotlin, S3] 백준 15649번 N과 M(1)

출처: unsplash.com

 

N과 M(1)(15649번)

Silver 3

#백트래킹

 

문제 내용

 

 

문제 접근

백트래킹을 이용해 해결 가능하다.

완전탐색으로도 해결할 수 있지만 백트래킹을 쓰는 게 공부에 도움이 될 것 같다.

 

1부터 n까지의 자연수 중 중복 없이 m개를 고르는 모든 경우를 출력한다.

백트래킹의 개념부터 간단하게 이야기하겠다.

 

백트래킹은 일자로 쭉 내려가다가 정답이 아님이 확실시되면 이전으로 돌아와서 다시 다른 경로로 검색을 시작하는 방법이다.

간단하게 사진으로 진행 과정을 봐보자.

사진 1-1

 

처음에는 0 -> 1 -> 3으로 이동하면서 탐색한다. 3에 도달하면 더 깊게 들어갈 수 없기 때문에 부모 노드로 다시 이동해서 다른 경로로 재탐색하는 방식이다.

 

부모 노드로 돌아가는 방법은 자식까지 dfs로 특정 깊이까지 들어가고 나면 저장하면서 방문 여부를 설정할 텐데 반복이 끝나고, 부모의 방문 여부를 해제하는 것으로 부모의 노드를 탐색할 수 있다. 하지만 이전에 들어갔던 곳은 이미 방문 처리가 되어 있기 때문에 들어가지 못하고, 다른 경로로 들어가게 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

private var res = arrayOf<Int>()
private var visited = booleanArrayOf()
private var num = 0
private var size = 0

private val sb = StringBuilder()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ").map { it.toInt() }
    num = input.first()
    size = input.last()
    res = Array(size) { 0 }
    visited = BooleanArray(num)

    dfs(0)

    println(sb)
}

private fun dfs(depth: Int) {
    if (depth == size) {
        for (r in res) {
            sb.append("$r ")
        }
        sb.append("\n")
        return
    }

    for (i in 0 until num) {
        if (!visited[i]) {
            visited[i] = true
            res[depth] = i+1
            dfs(depth + 1)

            visited[i] = false
        }
    }
}

 

문제 풀이

dfs로 백트래킹을 시작한다.

dfs에는 depth라는 얼마나 깊이 들어가는지 확인하는 파라미터만 받는다.

depth가 입력받은 size랑 같아지면 출력해야 한다.

 

방문 여부를 확인해 res에 넣어준다.

그리고 재귀 호출을 해준다.

재귀 호출이 끝난 다음에는 부모의 방문 체크를 해제한다.

 

 

문제 해결 과정

백트래킹은 처음이라 어렵다. 완전탐색으로도 풀 수 있어서 Silver 3인 듯하다. 백트래킹 연습용 문제이다.

같은 이름의 문제가 여러 개 있어 백트래킹 연습에는 좋을 것 같다.