1260번: DFS와 BFS

 

1260번: DFS와 BFS

 

DFS와 BFS

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

 

 

---

풀이 

 

DFS와 BFS의 차이를 이해하고 갈 수 있는 문제이다.

 

✏️ DFS

 

[Algorithm] - DFS(Depth-First Search)

 

DFS => 깊이 먼저 탐색

 

✏️ BFS

 

[Algorithm] - BFS(Breadth-First Search)

 

 

BFS => 너비 먼저 탐색

 

 

예제를 통해 DFS와 BFS 차이를 확인해보자.

 

1️⃣ DFS 

 

깊이 탐색이므로, 시작 정점이 1노드부터 시작하여 연결된 노드의 끝까지 탐색한다.

 

 

 

2️⃣ BFS

 

너비 탐색이므로, 시작 정점인 1노드와 인접한 노드들을 먼저 탐색한다.

 

 

 

 

 

---

구현

 

1️⃣ DFS 

 

• 스택과 재귀 방식 중 재귀 방식을 택했다.
• dfsvisited[] 배열로 각 정점 방문처리

 

func dfs(_ v: Int){
    dfsResult.append(v)
    dfsvisited[v] = true//해당 정점 방문

    for num in arr[v]{//현재 정점과 인접한 정점 방문
        if !dfsvisited[num]{//방문하지 않았다면
            dfs(num)//해당 정점으로 재귀
        }
    }
}

 

2️⃣ BFS

 

• queue 사용: 탐색중인 정점을 저장하고, 먼저 들어온 정점부터 처리
• bfsvisited[] 배열로 각 정점 방문처리

 

func bfs(_ v: Int){
    queue.append(v)//시작 정점 추가
    bfsResult.append(v)
    bfsvisited[v] = true//해당 정점 방문

    while !queue.isEmpty{//큐가 비어있지 않다면
        let currentNode = queue.removeFirst()

        for num in arr[currentNode]{
            if bfsvisited[num] {//방문했다면 무시
                continue
            }
            queue.append(num)//큐에 정점 추가
            bfsResult.append(num)
            bfsvisited[num] = true//해당 정점 방문처리
        }
    }
}

 

 

 

 

---

전체코드

 

 

 

let input = readLine()!.split(separator: " ").map{Int(String($0))!}

let (N,M,V) = (input[0], input[1], input[2])

var arr = [[Int]](repeating: [Int](), count: N + 1)


for _ in 1..<M+1{
    let edge = readLine()!.split(separator: " ").map{Int(String($0))!}

    let a = edge[0]
    let b = edge[1]

    arr[a].append(b)
    arr[b].append(a)
}

for i in 1..<N+1 {
    arr[i].sort()
}

var dfsResult: [Int] = []
var bfsResult: [Int] = []

var queue: [Int] = []

var dfsvisited = [Bool](repeating: false, count: N+1)
var bfsvisited = [Bool](repeating: false, count: N+1)


func bfs(_ v: Int){
    queue.append(v)
    bfsResult.append(v)
    bfsvisited[v] = true

    while !queue.isEmpty{
        let currentNode = queue.removeFirst()

        for num in arr[currentNode]{
            if bfsvisited[num] {
                continue
            }
            queue.append(num)
            bfsResult.append(num)
            bfsvisited[num] = true
        }
    }
}

func dfs(_ v: Int){
    dfsResult.append(v)
    dfsvisited[v] = true

    for num in arr[v]{
        if !dfsvisited[num]{
            dfs(num)
        }
    }
}

dfs(V)
bfs(V)

for value in dfsResult {
    print(value, terminator: " ")
}
print("")

for value in bfsResult {
    print(value, terminator: " ")
}