[BOJ/Swift] DFS와 BFS 1260

Baekjoon Online Judge

단계별로 풀어보기 / DFS와 BFS / DFS와 BFS 1260

문제에 모든 정보 및 저작권 https://www.acmicpc.net/

---

Todo:

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

Constraints:

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

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

Input-Output

)
(출처 : https://www.acmicpc.net/problem/1260)

Solution.swift

let inputs = readLine()!.split(separator: " ").map({Int(String($0))!})
var vertex =  [[Int]](repeating: [], count: inputs[0]+1)

for _ in 0..<inputs[1] {
    let nodes = readLine()!.split(separator: " ").map({Int(String($0))!})
    vertex[nodes[0]].append(nodes[1])
    vertex[nodes[0]].sort(by: <)
    vertex[nodes[1]].append(nodes[0])
    vertex[nodes[1]].sort(by: <)
}

func dfs(base: Int, visited: inout [Bool], _ result: inout [Int], _ vertex: inout [[Int]]) {
    if visited[base] {
        return
    } else {
        visited[base] = true
        result.append(base)

        vertex[base].forEach { next in
            dfs(base: next, visited: &visited, &result, &vertex)
        }
    }
}

func bfs(base: Int, _ result: inout [Int], _ vertex: inout [[Int]]) {
    var willVisit = [base]

    while let now = willVisit.popLast(), result.count < vertex.count - 1 {
        result.append(now)
        for next in vertex[now] {
            if !willVisit.contains(next), !result.contains(next) {
                willVisit.insert(next, at: 0)
            }
        }
    }
}
var dfsVertex = vertex, bfsVertex = vertex

// MARK: --- DFS
var visited = [Bool](repeating: false, count: inputs[0] + 1)
var dfsResult = [Int]()

dfs(base: inputs[2], visited: &visited, &dfsResult, &dfsVertex)
print( dfsResult.map({ String($0) }).joined(separator: " "))

// MARK: --- BFS
var bfsResult = [Int]()

bfs(base: inputs[2], &bfsResult, &bfsVertex)
print(bfsResult.map({ String($0) }).joined(separator: " "))

github Code Repository

How I tried this:

문제 자체는 DFS와 BFS의 기본 이해를 구현만 해내면 해결할 수 있는 문제였다.

기본적으로 인접행렬 형태로 그래프를 표현하고 진행했다.

DFS는 각 정점에 방문하면 해당 정점과 이어진 모든 정점에 접근 한다.
이미 방문한 곳에 도착하면 dfs() 함수를 마치도록 해둠

BFS는 각 정점에 방문하면 해당 정점과 이어진 모든 정점 중 방문하지 않은 정점을
다음 방문할 정점 큐에 쌓는다.
다음 방문할 정점 큐는 매번 쌓이고 줄어들다가 모두 비어질때 bfs()함수를 마친다

What I got is:

요즘들어 ! 사용에 대한 알고리즘에서 문제 또한 고민이 많아졌다.

간단해지는 방법에 고민을 위해서 [Int: (Bool,[Int])] 처럼 간단하게
딕셔너리를 이용해보려고 했는데.. 런타임 에러가 발생한다

정말 시간을 많이 쓰고 나서야 배열로 변경하니 런타임 에러도 없고 문제가 통과되었다.

I have to study:

• 알고리즘에서 강제 언래핑 없애는 방법?!
• DFS의 이해
• BFS의 이해

문제에 관한 모든 저작권 : https://www.acmicpc.net/