문제

백준 1260번
https://www.acmicpc.net/problem/1260

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

---

생각하기

코틀린으로 처음푸는 DFS/BFS 문제였다.
아무래도 자바로 개념은 알고있어서 생각보다 쉽게 풀렸다.

코드도 저번보다는 조금 더 정리가 됬지만, 효율성 부분에서는 개선이 되지않은게 조금 아쉽긴하다.

동작

private var arr = Array(0, {Array(0, {0})})
private var visit = Array(0, {false})

그래프를 모방해서 만들 2차원 배열 arr
노드의 방문 여부를 저장할 visit 배열 2개 생성

fun DFS(nodeNum : Int) {
    visit[nodeNum] = true;
    sb.append("${nodeNum} ");


    if(count == N) {
        return;
    }
    count ++;

    for(i in 1..N step 1) {
        if(arr[nodeNum][i] == 1 && !visit[i] ) {
            DFS(i);
        }
    }

} // End of DFS

DFS는 갈 수 있는 방향으로 타고타고 계속 넘어가므로, 보통 재귀나 stack을 통해서 구현을 하는데, 나는 재귀가 조금 더 익숙해서 재귀로 구현을 했다.

재귀로 구현을 하므로 처음 시작하면 nodeNum의 인덱스 위치에 있는 visit의 값을 true로 처리해준다. (방문을 했다는 뜻, 더 이상 방문하지 않음)

모든 노드를 방문하기 위해 N과 count가 같을 경우 탈출을 하도록 조건을 만들어 놓았다.
재귀에서는 탈출 조건이 꼭 필요하기 때문에 중요하다.

fun BFS(nodeNum : Int) {
    var que : Queue<Int> = LinkedList<Int>();
    que.offer(nodeNum);
    visit[nodeNum] = true;
    sb.append("${nodeNum} ");

    while( !que.isEmpty() ) {
        var nodeNum = que.poll();

        for(i in 1..N step 1) {

            if(arr[nodeNum][i] == 1 && !visit[i] ) {
                que.offer(i);
                visit[i] = true;
                sb.append("${i} ")
            }
        }
    }

    que.clear()
} // End of BFS

BFS는 Queue를 통해서 구현을 한다.
DFS는 한 뱡향으로 계속가지만, BFS는 갈 수 있는 곳을 미리 다 탐색해서 que에 집어 넣고, 모두 탐색한다.

---

코드

import java.io.*;
import java.util.*;

private var arr = Array(0, {Array(0, {0})})
private var visit = Array(0, {false})
private var sb = StringBuilder();

private var N : Int = 0; private var M : Int = 0;
private var count : Int = 0;

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )
    var st = StringTokenizer(br.readLine())

    N = st.nextToken().toInt(); // 정점의 개수
    M = st.nextToken().toInt(); // 간선의 개수
    var V = st.nextToken().toInt(); // 노드의 개수
    arr = Array(N+1, {Array(N+1, {0})})
    visit = Array(N+1, {false});


    for(i in 1..M step 1) {
        st = StringTokenizer(br.readLine())
        val x = st.nextToken().toInt();
        val y = st.nextToken().toInt();

        arr[x][y] = 1;
        arr[y][x] = 1;
    }

    DFS(V);
    sb.append('\n');

    visit = Array(N+1, {false});
    BFS(V);

    print(sb);
} // End of main

fun DFS(nodeNum : Int) {
    visit[nodeNum] = true;
    sb.append("${nodeNum} ");


    if(count == N) {
        return;
    }
    count ++;

    for(i in 1..N step 1) {
        if(arr[nodeNum][i] == 1 && !visit[i] ) {
            DFS(i);
        }
    }

} // End of DFS

fun BFS(nodeNum : Int) {
    var que : Queue<Int> = LinkedList<Int>();
    que.offer(nodeNum);
    visit[nodeNum] = true;
    sb.append("${nodeNum} ");

    while( !que.isEmpty() ) {
        var nodeNum = que.poll();

        for(i in 1..N step 1) {

            if(arr[nodeNum][i] == 1 && !visit[i] ) {
                que.offer(i);
                visit[i] = true;
                sb.append("${i} ")
            }
        }
    }

    que.clear()
} // End of BFS