백준 1260 DFS와 BFS - Swift

https://www.acmicpc.net/problem/1260

1260번: 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

예제 입력 2 

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

예제 출력 2 

3 1 2 5 4
3 1 4 2 5

예제 입력 3 

1000 1 1000
999 1000

예제 출력 3 

1000 999
1000 999

 

풀이 방법

1. 그래프 자료구조 형태 만들기
2. 그래프 탐색 (DFS, BFS) 구현

일단 기본적으로 그래프가 무엇인지? 그래프를 탐색하는 DFS, BFS가 무엇인지 알아야 풀 수 있는 문제 입니다.

예제 입력 1에 따라 DFS, BFS를 살펴보겠습니다.

 

DFS(Depth-first search) 

예제 입력 1 DFS

DFS는 깊이를 우선적으로 탐색하고 더 이상 깊이 갈 곳이 없으면 옆을 탐색합니다.

위 그림을 보면 1 -> (2,3,4) 다 연결되어 있습니다. 그런데 문제에서 조건이 가장 작은 정점부터 간다고 했으니까 2를 먼저 갑니다.

2 -> (1,4) 가 연결되어 있습니다. 그런데 1은 아까 방문했었죠? 그럼 4로 갑니다.

4 -> (2,3) 가 연결되어 있습니다. 2는 방문했었고 3으로 갑니다.

 

BFS(Breadth-first search) 

예제 입력 1 BFS

BFS는 넓이를 우선적으로 탐색하고 더 이상 가까운 노드가 없다면 그 다음 레벨(깊이)의 노드를 탐색 합니다.

위 그림을 보면 1 -> (2,3,4) 와 연결되어 있습니다. 그런데 문제에서 조건이 가장 작은 정점부터 간다고 했으니까 2를 먼저 갑니다.

아까 DFS와는 다르게 2에서 4로 깊게 가지 않고 1과 가까운 (3, 4) 중 적은 정점인 3으로 갑니다.

그다음에는 4로 갑니다. 이제 더 이상 가까운 것이 없으니 다음 레벨의 노드로 가려고 합니다.

아까 2를 다시 보면 2 -> (1,4) 이렇게 되있는데 이제 깊게 가는 거잖아요. 그런데 아까 이미 둘 다 방문 했었죠? 1 (시작점), 1 -> 4

그 다음 아까 3을 다시보면 3 -> (1, 4) 입니다. 마찬가지로 방문 했었습니다.

4 -> (1,2,3)도 마찬가지 입니다. 그러므로 BFS를 종료합니다.

 

코드

let NMV = readLine()!.split(separator: " ").map{ Int($0)! }
var gragh = [Int:[Int]]()

for _ in 0..<NMV[1] {
    let line = readLine()!.split(separator: " ").map{ Int($0)! }
    let start = line[0]
    let end = line[1]
    
    if gragh[start] == nil {
        gragh[start] = [end]
    } else {
        gragh[start]!.append(end)
    }
    
    if gragh[end] == nil {
        gragh[end] = [start]
    } else {
        gragh[end]!.append(start)
    }
}

var dfsAnswer = ""
var bfsAnswer = ""

// 작은 정점부터 들리기 위해서 내림차순으로 정렬 해줌
for key in gragh.keys {
    gragh[key]?.sort(by: >)
}

for i in dfs(NMV[2]) {
    dfsAnswer += "\(i) "
}

// 작은 정점부터 들리기 위해서 오름차순으로 정렬 해줌
for key in gragh.keys {
    gragh[key]?.sort(by: <)
}

for i in bfs(NMV[2]) {
    bfsAnswer += "\(i) "
}

print(dfsAnswer)
print(bfsAnswer)

func dfs(_ start: Int) -> [Int] {
    var visited = [Int]()
    var stack = [start] // DFS -> stack
    
    while stack.count > 0 {
        let node = stack.popLast()!
        
        if visited.contains(node) {
            continue
        } else {
            visited.append(node)
            if let nodes = gragh[node] {
                stack += nodes
            }
        }
    }
    
    return visited
}

func bfs(_ start: Int) -> [Int] {
    var visited = Array(repeating: false, count: NMV[0] + 1)
    var queue = [start] // DFS -> queue
    var index = 0
    var out = [Int]()
    visited[start] = true
    
    while queue.count > index {
    // removeFirst()는 O(n) 이기 때문에 index변수를 두어서 연산 속도를 올렸습니다.
        let node = queue[index]
        out.append(node)
        
        if let nodes = gragh[node] {
        
            for i in nodes {
                if !visited[i] {
                queue.append(i)
                    visited[i] = true
                }
            }
        }
        index += 1
        print(queue)
    }

     return out
}