백준 1260번 DFS와 BFS - kotlin

학부 시절 전공 시간에만 들어보고 손으로만 풀어봤던 DFS와 BFS 문제를 코딩으로 처음 접하게 되었다

​

바로 문제부터 살펴보면

​

문제

정점과 간선으로 이루어진 그래프를 DFS로 탐색했을 때, BFS로 탐색했을 때의 방문 순서를 출력하는 프로그램이다.

​

접근 방법

DFS는 스택, BFS는 큐를 사용하여 풀었던 학창시절의 기억을 되짚어서 접근하였다.

​

하지만 이론만 기억 날 뿐 손가락은 따라주지 않았고,,,, 다른 풀이를 참고했다.

​

​

풀이소스

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    //각 입력을 변수에 할당
    val (node, edge, start) = readLine().split(" ").map { it.toInt() }
    //그래프 선언
    val graph = Array(node + 1) { IntArray(node + 1) { 0 } }
    //방문체크 리스트 선언
    val visited = mutableListOf<Int>()

    //간선 수만큼 반복
    repeat(edge) {
        val (v1, v2) = readLine().split(" ").map { it.toInt() }
        //연결된 노드들의 관계인 인덱스의 값을 1로 설정정
        graph[v1][v2] = 1
        graph[v2][v1] = 1
    }

    dfs(start, graph, visited)
    visited.forEach {
        print("$it ")
    }

    visited.clear()

    println()
    bfs(start, graph, visited)
    visited.forEach {
        print("$it ")
    }
}

fun dfs(start: Int, graph: Array<IntArray>, visited: MutableList<Int>) {
    visited.add(start)

    for (y in 1 until graph.size) {
        //그래프가 연결되어있고, 아직 방문하지 않았으면
        if (graph[start][y] == 1 && !visited.contains(y)) {
            //연결되어있는 노드를 시작점으로 재귀호출
            dfs(y, graph, visited)
        }
    }
}

fun bfs(start: Int, graph: Array<IntArray>, visited: MutableList<Int>) {
    //큐 생성
    val queue = LinkedList<Int>()
    queue.add(start) //시작 노드, 큐 삽입
    visited.add(start) //방문체크

    //큐가 빈 상태가 될 때까지 반복
    while (!queue.isEmpty()) {
        val x = queue.poll()        //큐의 맨 앞을 삭제
        
        for (y in 1 until graph.size) {
            //그래프가 연결되어있고, 아직 방문하지 않았으면
            if (graph[x][y] == 1 && !visited.contains(y)) {                
                queue.add(y)//큐에 추가                
                visited.add(y) //방문체크
            }
        }
    }
}

마침

고향에 다녀와서 오랜만에 코딩을 해서 그런지 아직 능숙하지 않던 문법마저 가물가물 했다

거기다 이론만 기억나고 구현 방법은 모르는 BFS, DFS라서 시간을 많이 빼았겼지만 그 과정에서 다시한번 문법 공부도 하고, 좋은 기회였던것 같다.

아직도 헷갈리는 배열과 리스트의 선언과 사용법에 대하여 나중에 한 번 제대로 정리를 해야겠다.

​

오늘 BFS문제를 한개 더 풀었지만 피곤한 관계로 내일 일찍 작성해야겠다.