[알고리즘/Swift] 그래프탐색(DFS/BFS) - 타겟넘버, 네트워크, 단어변환, 여행경로

코테에서 제일 많이 다루는 DFS/BFS

1. 타겟 넘버 (DFS)

• 1을 더하거나 뺄 수 있기 때문에, 더하거나 빼는 경우에 대해 한번씩 DFS 를 수행해준다.
• 이를 그래프로 그려보면 이해하기 쉽다. 숫자를 하나 더하거나 빼는 것을 그래프의 깊이 탐색이라고 생각하면 된다.

그래프처럼 그려보기

import Foundation

func dfs(numbers: [Int], target: Int, i: Int, total: Int) -> Int {
    if i == numbers.count {
        return total == target ? 1 : 0
    }
    
    let count1 = dfs(numbers: numbers, target: target, i: i+1, total: total - numbers[i])
    let count2 = dfs(numbers: numbers, target: target, i: i+1, total: total + numbers[i])
    return count1 + count2
}

func solution(_ numbers:[Int], _ target:Int) -> Int {
    return dfs(numbers: numbers, target: target, i: 0, total: 0)
}

---

2. 네트워크 (DFS)

• 각 컴퓨터를 노드로, 컴퓨터가 연결된 네트워크를 그래프로 생각하면 된다.
• 특정 컴퓨터에서 시작해 연결된 모든 컴퓨터를 탐색하는 DFS 방식을 이용했다.
• visited 배열을 통해 방문한 노드를 체크한 후, 탐색하도록 했다.
• DFS 를 총 몇번 수행했는지 체크하면 네트워크의 개수를 찾을 수 있다.

import Foundation

// 네트워크 개수를 return -> DFS 로 같은 네트워크 전부 체크  
// computers[i][j] : i번과 j번이 연결되어있으면 1, 아니면 0 

func dfs(_ graph: [[Int]], _ visited: inout [Bool], _ i: Int) {
    if i == graph.count {
        return
    }
    visited[i] = true
    for (j, isConnect) in graph[i].enumerated() {
        if isConnect == 1 && !visited[j] {
            dfs(graph, &visited, j)
        }
    }
}

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    
    var visited = Array(repeating: false, count: n)
    var count = 0
    
    for i in 0..<n {
        if visited[i] == false {
            dfs(computers, &visited, i)
            count += 1
        }
    }

    return count
}

---

 

3. 단어 변환 (BFS)

• begin 단어는 words 배열에 없어, 이를 추가해주었다.
• 참고로 target 이 words 에 없다면 begin -> target 이 불가능하므로 0 을 반환한다.
• 주어진 words 를 통해 이웃 그래프를 만들었다. 단어가 하나만 차이나는 단어들을 연결해주는 그래프이다. (단어 50개이하)
• 이웃 그래프에 대해 BFS 를 수행한다. 가장 짧은 변환 과정을 찾는것이기 때문에 BFS 를 수행한다.
• depth 계산은 현재 노드에서 연결된 노드들을 queue 에 넣어줄 때, 현재 노드의 depth + 1 로 계산해준다. 
• 노드를 방문하는대로 단순히 계산해준다면, depth 를 계산할 수 없다. (오른쪽 그림의 검은색이 이에 해당, 빨간색이 Depth)
• 해당 문제에서는 테스트 1번이 통과하지 못해도, 채점이 가능한 에러가 있다. (1번도 통과되어야 맞는 풀이다 ..!)

오른쪽 그림에서 빨간색 숫자가 Depth 를 의미한다.

func getNeighbours(_ words: [String]) -> [[Int]] {
    let n = words.count
    var neighbours = Array(repeating: [Int](), count: n)
    for i in 0..<n {
        for j in i+1..<n {
            var count = 0
            zip(words[i], words[j]).forEach { (c1, c2) in
                if c1 != c2 { count += 1 }
            }
            if count == 1 {
                neighbours[i].append(j)
                neighbours[j].append(i)
            }
        }
    }
    return neighbours
}

/// BFS
func findShortestPath(_ neighbours: [[Int]], _ words: [String], _ target: String) -> Int {
    let n = neighbours.count
    var queue = [Int]()
    var depth = Array(repeating: 0, count: n)
    var visited = Array(repeating: false, count: n)

    queue.append(0)
    visited[0] = true
    while !queue.isEmpty {
        let current = queue.removeFirst()
        if words[current] == target {
            return depth[current]
        }
        for next in neighbours[current] {
            if visited[next] == false {
                visited[next] = true
                depth[next] = depth[current] + 1
                queue.append(next)
            }
        }
    }
    return 0
}

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {

    // Step0. 비긴도 단어에 추가, 타겟이 없는 경우 만들 수 없음
    guard words.contains(target) else {
        return 0
    }
    var words = words
    words.insert(begin, at: 0)

    // Step1. 알파벳 하나를 바꿔서 단어로 변환할 수 있는 경우, 이웃 노드로 설정!
    let neighbours = getNeighbours(words)

    // Step2. begin부터 시작하여 한 글자씩 바꿔나가면서 target이 되는 최소 경로를 찾기!
    return findShortestPath(neighbours, words, target)
}

 

---

4. 여행경로 (DFS)

• tickets 배열을 티켓의 도착지에 따라 오름차순 정렬한다. * 경로가 2가지 이상일 때 알파벳 순서가 앞서는 경로를 return
• 티켓을 사용했는지에 대해 visited 배열로 체크한다. * 주어진 항공권은 모두 사용해야한다.
• 티켓에 대해 DFS 수행 -> 가능한 경로를 반환한다. 
• DFS 수행시에, 모든 티켓을 소진해 경로를 만든 경우 course 배열을 반환한다. 경로가 더 이어지지 않는 경우 [] 를 반환.
• 주의사항) 같은 경로의 티켓이 중복되어 주어질 수 있다.

func findCourse(_ tickets: inout [[String]], _ visited: inout [Bool],
                _ src: String, _ course: [String]) -> [String] {

    if course.count == tickets.count+1 {
        return course
    }

    for (index, ticket) in tickets.enumerated() {
        if ticket[0] == src && visited[index] == false {
            visited[index] = true
            var newCourse = course
            newCourse.append(ticket[1]) // add dst
            let result = findCourse(&tickets, &visited, ticket[1], newCourse)
            if !result.isEmpty { return result }
            visited[index] = false
        }
    }
    return []
}

func solution(_ tickets:[[String]]) -> [String] {

    // 티켓의 도착지에 따라 오름차순 정렬.
    var tickets = tickets.sorted(by: { $0[1] < $1[1] })

    // 티켓을 사용했는지에 대해 visited 배열로 체크
    var visited = Array(repeating: false, count: tickets.count)

    // 티켓에 대해 DFS 수행 -> 가능한 경로를 반환한다.
    return findCourse(&tickets, &visited, "ICN", ["ICN"])
}

 

여행경로 반례

* 테스트케이스 1, 2 런타임에러에 대한 반례 포함

// 반례 1

print(solution([["ICN", "BBB"],["ICN", "CCC"],["BBB", "CCC"],["CCC", "BBB"],["CCC", "ICN"]]))

// ["ICN", "BBB", "CCC", "ICN", "CCC", "BBB"]

 

// 반례 2

print(solution([["ICN", "SFO"], ["SFO", "ICN"], ["ICN", "SFO"], ["SFO", "QRE"]]))

// ["ICN", "SFO", "ICN", "SFO", "QRE"]

 

// 반례 3

print(solution([["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]))

// ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]))

    

// 반례 4 * 런타임 에러 해결 (ZOO 에서 출발하는 티켓이 없어 딕셔너리접근x 런타임에러 발생)

print(solution([["ICN", "AOO"], ["AOO", "BOO"], ["AOO", "BOO"], ["BOO", "AOO"], ["BOO", "FOO"], ["FOO", "COO"], ["COO", "ZOO"]]))

// ["ICN", "AOO", "BOO", "AOO", "BOO", "FOO", "COO", "ZOO"]

---

* DFS / BFS 비교

같이 스터디하는 테일러 스위프트님이 정리해주신 내용