n과m 대표적인 백트래킹문제

백트래킹이라는 개념이 처음이라, 이 문제를 접했을땐 그저 bfs로 풀 생각을 했다.

 

백트래킹이란?

현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다. (bfs에서 필터가 걸린느낌?? 같다.)

---

n과m(1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

인풋이 4 2라면 돌아가는 로직을 간단하게 그려보았다.

코드 이해 ㅇ

안보고도 풀어 ㅇ

눈에 익히면서 다른 문제도 풀어보자

---

n과m(5)

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

만약 for문에 if문처럼 필터가 들어가지 않는다면 visited.count == m부분에서 마지막에 return을 걸어야 무한루프가 돌지 않는다.

당연한 얘기지만 또 시간을 투자할 미래의 나를 위해서..

---

n과m(9) (푸는중)

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

이거 왜 안풀리는지 모르겠다ㅜㅜ

시간초과나는 내 코드 

result를 String으로 받고 중복확인을 했는데 시간초과 >> Set<String>으로 중복확인 시간 단축까지 시켰는데

어디를 더 손봐야하는지 모르겠다 !! 

import Foundation
//15655 N과 M (6)

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
let nElements = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted()
var result = Set<String>()
var visited = [String]()
var arr = Array(repeating: 0, count: 10001)

for i in nElements {
    arr[i] += 1
}
let fixArr = arr

private func dfs() {
    if visited.count == m {
        result.insert(visited.joined(separator: " "))
        //두개가 되면 항상 리턴하여 다음 값을 받아와야 하니까 이 자리가 리턴이 맞음
        return
    }

    for i in nElements {
        if !visited.contains(String(i)){
            visited.append(String(i))
            dfs()
            visited.popLast()
            arr = fixArr
        }else if arr[i] >= 2 {
            arr[i] -= 1
            visited.append(String(i))
            dfs()
            visited.popLast()
            arr = fixArr
        }
    }
}

dfs()

for res in result.sorted() {
    print(res)
}