백준 1260 : DFS와 BFS

 

벨로그를 쓰다가 티스토리로 넘어왔다,, 그런 기념에서 첫번째 포스팅은 백준 코테 풀이로 . .

 

 

문제

 

문제는 이렇다.

예제 입력 예시들을 하나하나 트리로 그려보았는데 문제는 코드로 어떻게 구현해야 하는지를 모르겠다 ㅋ..ㅋ

 

 

아이디어

예제

 

위의 예제입력을 예시로 설명해보자면

 

DFS: 입력받은 정점번호를 기준으로 주어진 간선이 연결하는 두 정점의 번호에 주목한다. 

3이 탐색을 시작할 정점의 번호이므로, 3과 연결되는 정점들을 체크해준다. 그리고 거기서 왼쪽트리(3보다 작은 값이 연결된 정점에 주목)로 가게 되면 1이 체크된다. 그럼 1에서 또 연결 되는 정점들을 체크해보면 2가 나온다. 2와 연결된 정점은 5가 있다. 5와 연결된 정점은 4다. 

 

이렇게 DFS는  3-1-2-5-4 가 나오게 된다.

 

BFS : BFS는 너비우선 탐색이므로 3에서 탐색을 했을 때 3과 연결되는 모든 정점을 체크해줘야 한다. 3은 1이랑 4랑 연결되어 있고 1은 2, 4는 5랑 연결되어있다. 더이상 연결 될 정점들이 없다

 

따라서 BFS는 3-1-4-2-5 가 출력되게 된다.

 

문제는 이걸 어떻게 구현하지???? << 가 문제인데, 

DFS를 조건문을 써서 구현을 해야 하나.? 

 

도저히 모르겠어서 블로그를 참고 하였다. ㅎ..

 

dfs는 자식노드까지 파고 들어야 하기 때문에 재귀를 사용해서 구현해야 하고, bfs는 너비우선 탐색이므로 형제들의 노드를 기억해야 하기 때문에 큐를 사용해야 한다고 한다.

 

코드

import Foundation

var input = readLine()!.split(separator: " ").map { Int(String($0))! } //정수 여러개 입력받아서 띄어쓰기로 구분하기

let n = input[0] //정점
let m = input[1]  //간선
let v = input[2] //시작 정점

var visited = [Bool](repeating: false, count: n+1)
var graph = [[Int]](repeating: [], count:n+1)

for _ in 0..<m {
    let input = readLine()!.split(separator:" ").map {Int($0)!}
    let a = input[0], b = input[1]
    graph[a].append(b)
    graph[b].append(a)
}

graph = graph.map { $0.sorted() }

func dfs(node: Int) {
    visited[node] = true
    print(node, terminator: " ")

    for nextNode in graph[node] {
        if !visited[nextNode] {
            dfs(node: nextNode)
        }
    }
}

func bfs(node: Int) {
    var queue = [node]
    var index = 0
    visited[node] = true
    while queue.count > index {
        let currentNode = queue[index]
        print(currentNode, terminator: " ")

        for nextNode in graph[currentNode] {
            if !visited[nextNode] {
                visited[nextNode] = true
                queue.append(nextNode)
            }
        }
        index += 1
    }
}

dfs(node: v)
visited = [Bool](repeating: false, count: n+1)
print()
bfs(node: v)

 

dfs는 재귀함수를 통해 구현하였고, bfs는 큐를 사용하여 그래프를 탐색하도록 한다.

정점번호가 작은 순으로 방문하므로 인접 그래프를 정렬한다.

 

 

참고

https://dev-mandos.tistory.com/258