[Swift] 백준[15649번] N과 M(1) 문제풀이

백트래킹을 공부하면서 다시 한 번 풀어보는 문제입니다.

아직 백트래킹이 머리로는 이해 되는데 구현할 땐 헷갈려서 블로그 포스팅을 통해 저도 더 자세히 풀어 쓰면서 습득하고

보시는 분들도 이해되시길 바라며 작성하겠습니다!

 

https://www.acmicpc.net/status?from_mine=1&problem_id=15649&user_id=sangu522 

채점 현황

 

이게 제가 처음에 DFS인 줄 알고 풀었는데 백트래킹 문제인가봐요! 백준 알고리즘 분류에도 백트래킹이고 백트래킹을 공부하면서 예제로 나와서 다시 풀게 됐거든요.. 그래서 백트래킹과 DFS의 차이를 확실히 알기위해 검색해봤어요.

 

DFS: 완전 탐색을 기본으로 하는 그래프 순회 기법으로 가능한 모든 경로를 순회한다.

백트래킹: 경로 탐색 도중 해가 아니면 더 가지 않고 돌아와 다음 경로를 탐색합니다.

 

이 문제 같은 경우에 1~N까지 전체를 탐색하는게 아니라 선택된 수의 개수 K와 뽑을 개수 M이 같은 경우 탐색이 중단되고 다음 경로를 탐색하므로 백트래킹 기법이 되는 것 같습니다.

 

이제 풀어볼게요.

예제 1은 너무 간단하니까 예제 2로 백트래킹 기법을 사용할게요!

n = 4 , m = 2 일 때니까

arr은 길이 2의 순열을 구하면 출력해주면 되구요

check에는 1 2 3 4의 사용여부를 체크해주면 됩니다.

 

이제  백트래킹의 준비는 되었으니 백트래킹을 시작해봅시다!

1~n까지 반복합니다.

 

 

 

arr에 1을 넣어주고 1을 골랐으므로 check의 첫번째에 원소에 true을 넣어줍니다.

 

arr에 2를 넣어주고 check에 2번째 원소에 true를 넣어줍니다. arr이 다 찼으므로 더는 반복하지 않고 전 단계로 돌아갑니다.

 

 

전 단계로 돌아왔으니 이제 2말고 3을 넣어봅시다.

 

감이 좀 잡히시나요!? 이걸 코드로 구현하면 아래와 같습니다.

 

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n,m) = (input[0],input[1])

var arr = Array(repeating: 0, count: m)
var check = Array(repeating: false, count: n+1)

func dfs(_ k: Int) {
    if k == m {
        print(arr.map{ String($0) }.joined(separator: " "))
        return
    }
    
    for i in 1...n {
        if !check[i] {
            arr[k] = i;
            check[i] = true
            dfs(k+1)
            check[i] = false
        }
    }
}

dfs(0)

많이 풀다보면 익숙해지겠죠..?