[DFS] 경로탐색

문제

해결

import Foundation

var cnt = 0
var path = [Int]()
var g: [[Int]] = []
var ch: [Int] = []

func DFS(v: Int, n: Int) {
    if v == n {
        cnt += 1
        for x in path {
            print(x, terminator: " ")
        }
        print()
    } else {
        for i in 1...n {
            if g[v][i] == 1 && ch[i] == 0 {
                ch[i] = 1
                path.append(i)
                DFS(v: i, n: n)
                path.removeLast()
                ch[i] = 0
            }
        }
    }
}

func setupAndRunDFS(m: Int, n: Int, edges: [[Int]]) {
    g = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)
    ch = Array(repeating: 0, count: n + 1)
    
    for edge in edges {
        let a = edge[0]
        let b = edge[1]
        g[a][b] = 1
    }
    
    ch[1] = 1
    path.append(1)
    DFS(v: 1, n: n)
    print("Total paths: \(cnt)")
}

// Example usage
let exampleInput = [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 1],
    [2, 3],
    [2, 5],
    [3, 4],
    [4, 2],
    [4, 5]
]

setupAndRunDFS(m: 9, n: 5, edges: exampleInput)