백준1260번 DFS 와 BFS 코틀린

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

1260번: DFS와 BFS

 

안녕하세요! 대체공휴일 오후 

오늘은 백준에서 1260번 DFS 와 BFS 문제를 풀어봤습니다!

얼마전까지 그리디알고리즘 위주로 게속 풀다가 요번에는 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

 

---

이 문제는 간단하게 DFS와 BFS 알고리즘을 그냥 구현하는 되는 

즉 DFS 알고리즘 과 BFS 알고리즘을 알고 있는 사람들에게 있어서 비교적 쉬운 문제였습니다!

 

그래서 문제 풀이에 대한 설명은 생략하고 

각각의 알고리즘이 어떤 알고리즘인지 간략하게 설명하겠습니다!

---

DFS 알고리즘 

 

깊이 우선 탐색(DFS) 은 루트 노드 나 임의의 노드에서 시작하여 최대한 깊숙히 들어가서 탐색한 후 다시 원점으로 돌아가 다른 루트로 탐색하는 방식 

일반적으로 재귀호출을 사용 그러나 단순히 스택이나 인접행렬,인접리스트를 이용하여 구현하기도 함 

모든 노드를 방문하고자 하는 경우에 사용

 

BFS 알고리즘 

 

너비 우선 탐색(BFS) 은 "꼼꼼하게 좌우를 살피며 다니자"와 같이 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이라고 생각하면 쉽다! 

 

BFS 알고리즘은 보통 큐(queue) 를 이용해서 구현한다 

---

 

import java.util.*

var visited = booleanArrayOf()
var array : Array<IntArray> = arrayOf()
var strArray :List<String> = listOf()
fun main(){

    var str = readLine()

    strArray = str!!.split(" ")
    array = Array(strArray[0].toInt()){ IntArray(strArray[0].toInt()) }
    visited = BooleanArray(strArray[0].toInt())
    for(i in 0 until strArray[1].toInt()){
        var input = readLine()
        var temp = input!!.split(" ")

        array[temp[0].toInt()-1][temp[1].toInt()-1]= 1
        array[temp[1].toInt()-1][temp[0].toInt()-1]=1

    }
    visited.fill(false)
    dfs(strArray[2].toInt()-1)
    println("")
    visited.fill(false)
    bfs(strArray[2].toInt()-1)

}
fun dfs(v : Int){
    print("${v+1} ")
    visited[v] =true

    for(i in 0 until strArray[0].toInt()){
        if(array[v][i]!=0 && !visited[i]){
            dfs(i)
        }
    }

}

fun bfs(v : Int){
    val list : LinkedList<Int> = LinkedList()
    list.add(v)
    visited[v]=true
    print("${v+1} ")
    while (list.isNotEmpty()){
        val now = list.poll()

        for(i in 0 until strArray[0].toInt()){
            if(!visited[i] && array[now][i]!=0){
                list.add(i)
                visited[i]=true
                print("${i+1} ")
            }
        }
    }

}