백준 1260 DFS 와 BFS 구현하기

DFS 는 깊이 우선 탐색으로

1번노드가 시작점일시 1번의 자식들

그리고 그 자식들을 돌면서 깊게 먼저 탐색하는방식이다.

개인적으로 dfs 를 구현하기위해 재귀를 사용한다.

그리고 dfs 에는 필요한 요소들이있다

starting point : 몇번 노드를 탐색할지
array (graph) : 각 노드들의 자식 정보
visited array : 해당 노드를 이미 탐색했는지 정보
result : 계속 갱신될 결과값 

visited array 와 result 는 mutating 이 필요하다.

따라서 dfs 재귀 함수에는 inout 을 넣어줘야 한다.

func dfs(n:Int,arr : [[Int]],visited: inout [Int],dfsArr:inout [Int]){
    if(visited[n-1] == 1){
        return
    }
    visited[n-1] = 1
    dfsArr.append(n)
    for i in 0..<arr.count{
        if(arr[i].contains(n)){
            //1있는경우
            let nIndex = arr[i].firstIndex(of: n)
            if(nIndex==0){
                dfs(n: arr[i][1], arr: arr,visited: &visited,dfsArr: &dfsArr)
            }else{
                dfs(n: arr[i][0], arr: arr,visited: &visited,dfsArr: &dfsArr)
            }
        }
    }
}

var dfsVisited = Array(repeating: 0, count: count)
var dfsArr = [Int]()
dfs(n: start, arr: arr, visited: &dfsVisited, dfsArr: &dfsArr)

BFS는 너비우선탐색이므로 만약 1의 자식이 2, 3 이있다면

2의 자식을 탐색하기 전에 2, 3 을 모두탐색을 끝내야한다.

그러기 위해 QUEUE를 사용한다.

bfs에도 이런게필요하다.

starting point : 몇번 노드를 탐색할지
array (graph) : 각 노드들의 자식 정보
visited array : 해당 노드를 이미 탐색했는지 정보
queue : 작업의 순서를 저장 

2와 3을 큐에 담고 2의 자식과 3의 자식은 그다음 순서에 넣어 줌으로써

순서대로 탐색 할수있다.

func bfs(start:Int,arr : [[Int]]){
    var answer = [Int]()
    var visited = Array(repeating: 0, count: count)
    var queue = [start]
    
    while !queue.isEmpty {
        let number = queue.removeFirst()
        if(visited[number-1]==1){
            continue
            
        }
        //인접 노드들 큐에 추가
        for i in 0..<arr.count{
            if(arr[i].contains(number)){
                let numberIndex = arr[i].firstIndex(of: number)
                if(numberIndex == 0 ){
                    queue.append(arr[i][1])
                }else{
                    queue.append(arr[i][0])
                }
            }
        }
        //visited처리
        visited[number-1] = 1
        //배열에 추가
        answer.append(number)
    }
    print(answer)
}