Swift 알고리즘 : DFS & BFS

DFS

깊이 우선 탐색

스택 재귀 사용, 연결 요소 찾기 쉬움

func dfs(graph: [[Int]], v: Int, visited: inout [Bool]){
    //현재 노드 방문 처리
    visited[v] = true
    print(v, terminator: " ")
    
    //현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v] {
        if !visited[i]{
            dfs(graph: graph, v: i, visited: &visited)
        }
    }
}

let graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

var visited = Array(repeating: false, count: graph.count)


dfs(graph: graph, v: 1, visited: &visited)

//예시 문제 : 0으로만 인접되어 있는 구간 표시하기

let n = 4
let m = 5
var graph = [[0,0,1,1,0],
             [0,0,0,1,1],
             [1,1,1,1,1],
             [0,0,0,0,0]]
var result = 0


func dfs(_ x: Int, _ y: Int) -> Bool{
	//범위를 벗어나면 멈추기
    if x <= -1 || x >= n || y <= -1 || y >= m{
        return false
    }
    
    //방문하지 않았으면 1
    if graph[x][y] == 0{
        graph[x][y] = 1
        
        //상하좌우를 방문처리하고 재귀
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        
        //인접을 다 1로 만들었으면 리턴 트루
        return true
    }
    
    return false
}


for i in 0..<n{
    for j in 0..<m{
    	//dfs를 돌아 참일때만 += 1
        if dfs(i, j) == true{
            result += 1
        }
    }
}

print(result)

BFS

너비 우선 탐색 (가까운 노드부터 탐색)

큐 사용, 최단 경로 알기 쉬움

func bfs(graph: [[Int]], start: Int, visited: inout [Bool]){
    var queue = [start]
    //현재 노드 방문 처리
    visited[start] = true
    
    //큐가 빌 때까지 반복
    while !queue.isEmpty{
        //큐에서 하나의 원소 뽑아 출력
        let v = queue.removeFirst()
        print(v, terminator: " ")
        //방문하지 않은 인접한 원소들을 큐에 추가
        for i in graph[v]{
            if !visited[i]{
                queue += [i]
                visited[i] = true
            }
        }
    }
}

let graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

var visited = Array(repeating: false, count: graph.count)


bfs(graph: graph, start: 1, visited: &visited)

//예시문제
//1이 길 0이 벽인 미로에서 첫번째에서 마지막까지 갔을 때 미로 최단 경로 구하기
let n = 5
let m = 6
var graph = [[1,0,1,0,1,0],
             [1,1,1,1,1,1],
             [0,0,0,0,0,1],
             [1,1,1,1,1,1],
             [1,1,1,1,1,1]]
//상하좌우
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]


func bfs(_ x: Int, _ y: Int) -> Int{
    var queue = [(x, y)]
    
    while !queue.isEmpty{
        let xy = queue.removeFirst()
        let x = xy.0
        let y = xy.1
        
        for i in 0..<4{
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || nx >= n || ny < 0 || ny >= m{
                continue
            }
            if graph[nx][ny] == 0{
                continue
            }
            if graph[nx][ny] == 1{
                graph[nx][ny] = graph[x][y] + 1
                queue += [(nx, ny)]
            }
        }
    }
    
    graph.forEach{
        print($0)
    }
    return graph[n - 1][m - 1] // 마지막 왔을 때 최단 거리 반환
}

print(bfs(0, 0))