[백준/BOJ] 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의 기본을 알 수 있는 문제라고 생각한다.

https://jjunsu.tistory.com/195

[알고리즘] 그래프 탐색(Graph Search) /BFS, DFS

bfs와 dfs의 개념은 위의 작성글을 참고하면 좋을 것 같다.

 

예제 입력1을 토대로 보자.

두 정점이 연결되어 있다면 1, 연결되어 있지 않다면 0으로 표시한다.

또한 dfs bfs를 진행할 때는 방문여부를 확인할 visited 배열이 있어야 한다.

visited 배열은 종점의 개수만큼 크기를 선언해주면 된다.

 

이제 dfs 함수부터 살펴보자.

dfs 함수는 재귀, 스택을 활용하여 구현할 수 있는데, 나는 재귀를 이용하는 방법을 선택하였다.

depth first search라는 이름에 맞게 가능한 깊이 탐색을 한 후, 다음으로 넘어간다.

우선 시작 정점이 1이므로 visted[1]을 true로 선언해준다.

1과 연결된 정점 중 가장 근접해있는 정점은 2이다.

따라서 visited[2] = true가 된다.

 

이제 2와 연결된 정점을 살펴보자.

1과 연결이 되있지만 이미 방문했던 지점이므로 지나치면 된다.

이후 정점 3은 연결이 안되있고, 4와 연결되있는 것을 확인할 수 있다.

따라서 visited[4] = true가 된다.

 

4와 연결된 정점 중 정점 1과 정점 2는 이미 방문했던 정점이므로 아직 방문을 하지 않았던 정점 3에 방문하게 된다.

이렇게 하여 모든 정점의 방문이 끝났다.

결과적으로는 1 → 2 → 4 → 3의 순서로 방문하는 것을 알 수 있다.

 

다음으로 bfs를 살펴보자.

bfs는 큐를 이용하여 구현한다.

breath first time으로 먼저 가능한 넓게 탐색을 한 후, 다음으로 넘어간다.

위의 예시를 다시 봐보면, 정말 간편하게 탐색이 끝나는 것을 알 수 있다.

1 → 2 → 3 → 4의 순서로 방문하는 것을 확인할 수 있다.

 

물론 모든 bfs 문제가 위와 같이 단순한 탐색으로 끝나는 것은 아니다.

예제 입력 2로 보면, 좀 더 복잡한 경우의 bfs 탐색을 볼 수 있다.

시작 정점이 3이므로 3에서부터 탐색을 시작해보자.

우선 정점 3을 큐에 넣어준 후, 큐가 빌 때까지 반복을 할 것이다.

이는 코드를 보며, 이해하는 편이 더 좋을 것이라 생각한다.

 

반복이 시작되면 큐의 맨 앞에 있는 요소를 꺼낸다.

이 요소는 3일 것이고, 이와 연결된 정점을 찾으면 1과 4가 있는 것을 확인할 수 있다.

따라서 3 → 1 → 4의 순으로 방문한 것을 알 수 있다.

 

방문한 각 정점은 큐에 넣어주고, 방문여부를 true로 바꿔준다.(visited[1] = true, visited[4] = true)

정점 3과 연결된 정점을 전부 탐색했으니 큐의 맨 앞에 있는 요소를 꺼내준다.

이번 요소는 1이 될 것이다.

 

정점 1과 연결된 정점은 2와 3이 있는 것을 알 수 있다.

이 중 정점 3은 시작 정점이었으므로 이미 방문을 했던 정점이다.

따라서 정점 2만 큐에 넣고, 방문여부를 체크해준 후, 넘어가면 된다.

이 과정을 거치면 정점 1과 연결된 정점도 모두 탐색이 완료된다.

 

이를 계속 반복할 것이다.

정점 1에서 방문할 정점이 없으므로, 큐의 맨 앞 요소를 꺼낸다.

이 요소는 4이고, 정점 4와 연결된 정점을 확인한다.

정점 3과 5과 연결되있는 것을 확인할 수 있다.

3은 이미 방문했던 정점이므로 지나치고 정점 5에 방문하게 된다.

 

이제 모든 정점을 다 방문하였다.

bfs의 방문 순서는 3 → 1 → 4 → 2 → 5인 것을 확인할 수 있다.

 

bfs의 설명이 부실할 수 있다 생각하여 코드를 참조하는 것을 추천한다.

소스 코드

import java.util.*

lateinit var visited: BooleanArray
lateinit var arr: Array<IntArray>

fun main() = with(System.`in`.bufferedReader()){
    val (nodeCnt, edgeCnt, startNode) = readLine().split(" ").map { it.toInt() }
    arr = Array(nodeCnt+1) { IntArray(nodeCnt+1) }
    visited = BooleanArray(nodeCnt+1)
    for(i in 0 until edgeCnt) {
        val (node1, node2) = readLine().split(" ").map { it.toInt() }
        arr[node1][node2] = 1
        arr[node2][node1] = 1
    }
    dfs(startNode, nodeCnt)
    println()
    for(i in 0 .. nodeCnt) visited[i] = false
    bfs(startNode, nodeCnt)
}

fun dfs(now: Int, nodeCnt: Int) {
    print("$now ")
    visited[now] = true
    for(i in 1 .. nodeCnt) {
        if(arr[now][i] == 1 && !visited[i]) {
            dfs(i, nodeCnt)
        }
    }
    return
}

fun bfs(now: Int, nodeCnt: Int) {
    print("$now ")
    visited[now] = true
    val que: Queue<Int> = LinkedList()
    que.offer(now)
    while(!que.isEmpty()) {
        val top = que.poll()
        for(i in 1 .. nodeCnt) {
            if(arr[top][i] == 1 && !visited[i]) {
                print("$i ")
                que.offer(i)
                visited[i] = true
            }
        }
    }
    return
}