[swift - algorithm] 순열과 조합 (dfs로 구현), bfs, dfs, 백트래킹, 재귀

순열과 조합 (완전탐색 DFS)

- 순열은 (1, 2), (2, 1) 다른 것: 순서도 고려한 것

   조합은 (1, 2), (2, 1) 같은 것: 순서는 고려하지 않은 것

 

- 구현 시 차이점은 for문: 

  조합: for문 시작점이 dfs에서 들어오는 것

  순열: for문 시작점이 0부터

 

* 데이터

let rawData = "0123"
let data = rawData.map { String($0) }
var visit = [Bool](repeating: false, count: data.count)

1) 조합

// 4C2

dfs_comb(data: data, curInd: 0, curCnt: 0, targetCnt: 2, answer: "")

func dfs_comb(data: [String], curInd: Int, curCnt: Int, targetCnt: Int, answer: String) {
    if curCnt == targetCnt {
        print(answer)
    }

    for i in curInd..<data.count {
        if !visit[i] {
            visit[i] = true
            dfs_comb(data: data, curInd: i, curCnt: curCnt + 1, targetCnt: targetCnt, answer: answer + data[i])
            visit[i] = false
        }
    }
}

/*
 01
 02
 03
 12
 13
 23
 */

 

2) 순열

 - visited사용 후 for문 시작이 항상 1부터(또는 0) 

// 4P2

dfs(data: data, curInd: 0, curCnt: 0, targetCnt: 2, answer: "")

func dfs(data: [String], curInd: Int, curCnt: Int, targetCnt: Int, answer: String) {
    if curCnt == targetCnt {
        print(answer)
        return
    }

    for i in 0..<data.count {
        if !visit[i] {
            visit[i] = true
            dfs(data: data, curInd: i, curCnt: curCnt + 1, targetCnt: targetCnt, answer: answer + data[i])
            visit[i] = false
        }
    }
}

/*
 01
 02
 03
 10
 12
 13
 20
 21
 23
 30
 31
 32
 */

단순 dfs, bfs

1) dfs

1. 방문
2. 방문할 리스트 for
3. 정해진곳 방문 후 1번으로 다시

func dfs(_ start: Int) {
    visit[start] = true // 1.방문
    print(start, terminator: " ")

    // 2. 방문할 리스트
    for end in 1...N { 
        if map[start][end] == 1, !visit[end] {
            visit[end] = true
            dfs(end) // 3. 정해진곳 방문 후 1번으로 다시
        }
    }
}

 

2) bfs

1. 방문
2. 근처 노드들을 Queue에 삽입
3. Queue에서 하나 빼낸 후 다시 1번부터 시작

// bfs주의사항 - removeFirst()안쓰고 idx 쓰기
func bfs() {
  var q = [Int]()
  var ans = ""
	var idx = 0
  q.append(s)
  var visited = [Bool](repeating: false, count: n+1)
  visited[s] = true
  
  while idx < q.count {
    idx += 1
    ans = ans + "\(next) "
    
    for val in arr[next] where !visited[val] {
      q.append(val)
      visited[val] = true
    }
  }
  
  print(ans)
}

visit[i] = true, visit[i] = false의 이해

• if 문 안에서 visit[i] = false로 다시 되돌리는 이유는 visit가 전역변수 or inout이므로 되돌리는 것
• 만약 visit가 call by value이면 visit[i] = false가 필요 없는 코드

dfs의 종류 3가지

• 일반 재귀 호출: 프로그래머스 타겟넘버

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    let ret = cal(numbers: numbers, ind: 0, sum: 0, target: target)
    return ret
}

func cal(numbers: [Int], ind: Int, sum: Int, target: Int) -> Int {
    if ind == numbers.count {
        return sum == target ? 1 : 0
    }
    
    let v1 = cal(numbers: numbers, ind: ind + 1, sum: sum + numbers[ind], target: target)
    let v2 = cal(numbers: numbers, ind: ind + 1, sum: sum - numbers[ind], target: target)
    return v1 + v2
}

• 일반 dfs: 프로그래머스 네트워크

import Foundation

var N: Int!
var map: [[Int]]!
var visit: [Bool]!
var answer = 0

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    N = n
    map = computers
    visit = [Bool](repeating: false, count: N)
    for i in 0..<N {
        if !visit[i] {
            answer += 1
            dfs(start: i)
        }
    }
    
    return answer
}

func dfs(start: Int) {
    visit[start] = true
    
    for i in 1..<N {
        if !visit[i], map[start][i] == 1 {
            visit[i] = true
            dfs(start: i)
        }
    }
}

• 백트래킹 (branch and bound): 프로그래머스 N으로 표현
  • 백트래킹 이해: 재귀를 부르는 횟수만큼 child가 생기는 트리를 연상

재귀의 형태

import Foundation

let maxVal = 9
var minDepth = 9

func solution(_ N:Int, _ number:Int) -> Int {
    dfs(N, number, 0, 0)
    return minDepth == maxVal ? -1 : minDepth
}

func dfs(_ N: Int, _ number: Int, _ cnt: Int, _ val: Int) {
    if cnt >= maxVal {
        return
    }
    
    if val == number {
        minDepth = min(minDepth, cnt)
        return
    }
    
    var oper = 0
    for i in 1...9 {
        oper = oper * 10 + N
        dfs(N, number, cnt + i, val + oper)
        dfs(N, number, cnt + i, val - oper)
        if oper != 0 {
            dfs(N, number, cnt + i, val * oper)
            dfs(N, number, cnt + i, val / oper)
        }
    }
}

* 문제

- dfs vs bfs: www.acmicpc.net/problem/1260

- 조합: www.acmicpc.net/problem/1260

- 순열: www.acmicpc.net/problem/1722