백준[10974] - 모든 순열 (Kotlin)

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val N = br.readLine().toInt()
    val visited = Array(N+1) { 0 }
    val selected = Array(N) { 0 }

    fun dfs(k: Int) {
        if (k >= N) {
            for (i in selected.indices) bw.write("${selected[i]} ")
            bw.write("\n")
            return
        }

        for (i in 1..N) {
            if (visited[i] == 1) continue
            selected[k] = i
            visited[i] = 1
            dfs(k+1)
            selected[k] = 0
            visited[i] = 0
        }
    }

    dfs(0)
    bw.flush()
    bw.close()
    br.close()
}

 

각 값의 중복 사용을 체크하기 위한 visited 배열, 선택한 값을 저장, 출력하기 위한 selected 배열을 활용한다.

각 자리마다 1~N까지 값을 넣으며 백트래킹을 수행한다.

visited[i]의 값을 확인하여 중복 사용을 체크한 후, 중복 사용일 시 continue로 해당 값을 패쓰한다.

 

고찰 : N과 M 시리즈 문제를 다 풀어봐서, 순열 관련 백트래킹 문제였던 본 문제는 비교적 쉽게 풀 수 있었다.

 

걸린 시간 : 5분

난이도 : 실버 3

문제 : https://www.acmicpc.net/problem/10974

10974번: 모든 순열