[알고리즘] Swift -백준 #1260(DFS와 BFS)

문제링크

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부터 방문된 점을 순서대로 출력하면 된다.

 

 

---

분석

그래프를 DFS 와 BFS 결과를 출력하시오

방문 점이 여러개 일 경우 작은 번호부터 방문

더 이상 방문할 수 없으면 종료

 

풀이 과정

n = 정점의 개수, m = 간선의 개수, v = 탐색을 시작할 번호

m개의 줄 = 간선을 연결하는 정점의 번호 (두 정점 사이에 여러 개의 간선이 있을 수 있다.

 

DFS 푸는 방법 - 재귀

BFS 푸는 방법 - 큐

 

풀이

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

let n = input[0]
let m = input[1]
let v = input[2]

var checkArr = Array(repeating: false, count: n+1)
var arr = Array(repeating: Array(repeating: false, count: n+1), count: n+1)

for _ in 0..<m {
    let line = readLine()!.split(separator: " ").map{ Int($0)!}
    
    //양방향 간선
    arr[line[0]][line[1]] = true
    arr[line[1]][line[0]] = true
}

func dfs(_ v: Int) {
    checkArr[v] = true
    
    print(v, terminator: " ")
    for i in 1..<n+1 {
        if checkArr[i] == false && arr[v][i] == true {
            dfs(i)
        }
    }
}

func bfs(_ v: Int) {
    var q = [Int]()
    
    checkArr[v] = false
    q.append(v)
    
    while !q.isEmpty {
        var v2 = q.removeFirst()
        print(v2, terminator: " ")
        
        for i in 1..<n+1 {
            if checkArr[i] == true && arr[v2][i] == true {
                q.append(i)
                checkArr[i] = false
            }
        }
    }
}

dfs(v)
print("")
bfs(v)

큐를 이용하지 않고 배열을 이용하여 removeFirst() 를 사용하였다.

배열에서 첫번째 요소를 삭제하는 일은 시간복잡도가 크기 때문에 시간초과가 날 수 있다.

첫번째 요소와 마지막 요소를 자유롭게 삽입 삭제가 가능한 덱을 이용하여 구현할 수 있다.

class Dequeue<T: Comparable> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
    func firstIndex(_ num: T) -> Int {
        let newQue = deQueue.reversed() + enQueue
        if let i = newQue.firstIndex(where: {$0 == num}) {
            return i
        }
        return 0
    }
}


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

let n = input[0]
let m = input[1]
let v = input[2]

var checkArr = Array(repeating: false, count: n+1)
var arr = Array(repeating: Array(repeating: false, count: n+1), count: n+1)

for _ in 0..<m {
    let line = readLine()!.split(separator: " ").map{ Int($0)!}
    
    //양방향 간선
    arr[line[0]][line[1]] = true
    arr[line[1]][line[0]] = true
}

func dfs(_ v: Int) {
    checkArr[v] = true
    
    print(v, terminator: " ")
    for i in 1..<n+1 {
        if checkArr[i] == false && arr[v][i] == true {
            dfs(i)
        }
    }
}

func bfs(_ v: Int) {
    var deq = Dequeue<Int>([])

    checkArr[v] = false
    deq.pushLast(v)
    
    while !deq.isEmpty {
        var v2 = deq.popFirst()
        print(v2, terminator: " ")
        
        for i in 1..<n+1 {
            if checkArr[i] == true && arr[v2][i] == true {
                deq.pushLast(i)
                checkArr[i] = false
            }
        }
    }
}

dfs(v)
print("")
bfs(v)

 

결과

 

 

알게된 점

기본적인 DFS 와 BFS의 문제이다.

DFS는 재귀를 사용하고 

BFS는 큐를 사용하여 구현하였다.

이를 응용하여 다른 문제를 풀어봐야겠다.

 

DFS

일단 처음에 방문체크를 할 배열을 생성해준다.

함수를 만들고 시작하는 좌표를 파라미터로 넣어준다.

방문하는 좌표를 방문체크를 true로 변경한다.

그 다음 반복문을 돌려서 방문하지 않은 곳이면서 다음으로 갈 위치를 다시 확인한다.

 

BFS

일단 처음에 방문체크를 할 배열을 생성해준다.

함수를 만들고 시작하는 좌표를 파라미터로 넣어준다.

방문하는 좌표를 방문체크를 true로 변경한다.

새로운 큐를 하나 생성하고 방문하는 좌표를 추가한다.

큐에 들어있는 좌표를 하나씩 꺼내면서 확인을 해야하기 때문에 큐가 비어있을 때까지 반복문을 돌려서 다음으로 갈 위치를 큐에 추가해준 후 방문체크를 하여 true로 변경시켜준다.