[Swift][DFS/BFS] 백준 1260번 (DFS와 BFS)

요구능력: DFS와 BFS 그리고 스택과 큐의 이해

 

코드설명 : 

 

1.

간선을 받기위함.
이렇게 받으면 a[0]이 시작노드 a[1]이 도착노드인데 서로 넣어준 이유는 간선이 양방향이기때문이다.
예를 들면 간선이 1 5 로 입력되었으면 a[0]가 1이고 a[1]이 5이다.
여기서 a[0]에만 5를 넣어주면 간선은 1->5는 갈수있는데 5->1은 못가는게 된다.
정렬해준 이유는 문제에 순서가 적혀있었기 때문이다.
마찬가지로 둘다 정렬해준 이유는 간선입력이 a[0] = 1, a[1] = 5가 있는데 간선으로 입력받는것중 5로시작하는게 없을경우 정렬이 안되기 때문이다.

 

2.

시작노드는 시작이기 때문에 당연히 방문처리를 한다.

그리고 방문한 노드를 바로 프린트 해주는 방식으로 했다.

DFS는 깊이우선 탐색이기 때문에 말그대로 깊이가 있는 부분을 우선적으로 탐색한 것이다.

 

3.

시작노드는 시작하면서 방문하기 때문에 방문처리를 해주고

BFS는 너비우선 탐색으로 가까이 있는 것들 먼저 탐색을 한다.

Queue를 이용해서 탐색을한다.

처음에 큐에 시작노드를 넣어두고 큐가 비워질때 까지 루프를 도는데,

큐에서 deque()하는 노드의 인접노드를 큐에 넣어주는 방식이다.

이런식으로 큐가 비워지면 BFS탐색은 끝이난다.

 

후기 : 이렇게 기본적인거 구현하는것도 솔직히 버겁다..

응용하게되면 멘탈 바사삭....이겠지..?

이해가 안가는부분이나 태클거실 부분들을 댓글로 적어주세요.

let arr = readLine()!.split(separator: " ").map{Int($0)!}
let n = arr[0]
let m = arr[1]
var v = arr[2]

var graph: [[Int]] = Array(repeating: [], count: n + 1) //이차원 배열을 [i][j]라고 한다면 [i]는 시작노드, [j]는 도착노드
var visited = Array(repeating: false, count: n + 1) //방문여부 저장
var queue = Queue<Int>() //아래 선언한 Queue구조체를 가져왔다.

for _ in 1...m{ //1번
    let a: [Int] = readLine()!.split(separator: " ").map{Int($0)!}
    graph[a[0]].append(a[1])
    graph[a[1]].append(a[0])
    graph[a[0]].sort()
    graph[a[1]].sort()
}
DFS(graph, v, &visited)
visited = Array(repeating: false, count: n + 1) //초기화 해줘야 BFS에서 써먹는다.
print("")
BFS(graph, &v, &visited)

func DFS(_ graph: [[Int]], _ v: Int, _ visited: inout [Bool]){//2번
    visited[v] = true
    print(v,terminator: " ")
    
    for i in graph[v]{
        if !visited[i] {
            DFS(graph, i, &visited)
        }
    }
}


func BFS(_ graph: [[Int]], _ v: inout Int, _ visited: inout [Bool]){//3번
    visited[v] = true
    queue.enque(v)
    
    while !queue.isEmpty(){
        v = queue.deque()
        print(v, terminator: " ")
        
        for i in graph[v]{
            if !visited[i] {
                queue.enque(i)
                visited[i] = true
            }
        }
    }
}

struct Queue<T>{
    var queue :[Int] = []
    mutating func enque(_ x: Int){
        queue.append(x)
    }
    mutating func deque() -> Int{
        if !queue.isEmpty{
            queue.reverse()
            let a = queue.removeLast()
            queue.reverse()
            return a
        }else {
            return 0
        }
    }
    func isEmpty() -> Bool {
        return queue.isEmpty
    }
}