[BOJ-2210][백준 2210] 숫자판 점프 [SILVER-2][Solved by Kotlin]

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력 및 출력

• 입력: 다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.
• 출력: 첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

풀이

숫자판을 모든 점에서 인접해 있는 네 방향으로 다섯 번 이동하면서 여섯자리 숫자를 얻어낸다. 숫자판을 이동하기 위해 DFS(깊이우선 탐색) 알고리즘을 통해 탐색한다.  

  
보통 그래프 탐색을 할 때에는 visited배열을 두어 탐색한 곳을 저장해두어 다음에는 탐색한 곳을 재탐색하지 않도록하는데, 문제에서 한 번 거쳤던 점을 다시 거쳐도 된다고 하였으니 방문한 점은 고려하지 않아도 된다.  

이렇게 찾은 여섯자리 숫자를 리스트에 모두 추가한다.

여섯 자리 숫자중 중복되는 숫자가 있을 수 있기 때문에 List-> Set으로 변경하고 그 개수를 세면 답을 얻을 수 있다.

코드

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*

val bw = BufferedWriter(OutputStreamWriter(System.out))
// 그래프 및 여섯자리 숫자를 받을 집합을 선언한다.
lateinit var graph: Array<IntArray>
lateinit var resultSet: MutableSet<String>
lateinit var tmp: MutableList<Char>
fun main() = with(System.`in`.bufferedReader()) {
    // 그래프 초기화
    graph = Array(5) { IntArray(5) {0} }
    // DFS수행 중 완성된 6자리 숫자를 담을 리스트 초기화
    tmp = MutableList<Char>(6){'0'}
    // 집합 초기화
    resultSet = mutableSetOf()
    // 반복문을 통해 입력값을 그래프에 대입한다.
    for(i in 0 until 5){
        val list = readLine().split(" ").map{ it.toInt() }
        for(j in list.indices) {
            graph[i][j] = list[j]
        }
    }
    // 모든 점에서 DFS 알고리즘을 수행한다.
    for (i in 0 until 5) {
        for (j in 0 until 5) {
            dfs_2210(0, i, j)
        }
    }

    // 결과 집합의 개수를 출력한다.
    bw.write("${resultSet.size}")

    bw.flush()
    bw.close()
    close()
}

fun dfs_2210(length: Int, x:Int, y:Int) {
    // 1. 여섯자리가 완성 될 때
    if(length == 6) {
        val res = "${tmp[0]}${tmp[1]}${tmp[2]}${tmp[3]}${tmp[4]}${tmp[5]}"
        resultSet.add(res)
    } else { // 2. 그 이외
        if (x < 0 || x >= graph.size || y < 0 || y >= graph[0].size)
            return
        tmp[length] = graph[x][y].toChar()
        dfs_2210(length + 1, x, y - 1)
        dfs_2210(length + 1, x, y + 1)
        dfs_2210(length + 1, x - 1, y)
        dfs_2210(length + 1, x + 1, y)
    }
}

DFS 알고리즘

DFS 알고리즘이란 그래프를 탐색할 때 한 방향으로 갈 수 있을 때 까지 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그곳으로부터 다시 다른 방향으로 갈 수 있을 떄까지 탐색을 반복하는 알고리즘이다.

 

본 문제에서는 다음과 같이 적용했다.

먼저 DFS가 실행되는 else절을 확인한다. (문제 조건 상 사방 탐색을 사용하였다.)
재귀함수를 통해 DFS를 구현할 수 있는데, 먼저, 현재 x, y좌표에서 (x, y-1) 방향으로 계속 탐색을 한다.

하단방향으로 탐색을 하다가 그래프 범위를 벗어났을 때, return을 하여, 다음 재귀함수를 실행하게 되고, (x, y+1) 우측 방향으로 계속 탐색을 한다.
(탐색을 하기 전에 먼저 tmp배열의 현재 좌표의 숫자를 기록하여 정답을 만들어가도록 하였다.)
이렇게 한 방향으로만 탐색을 하면서 글자를 추가해 나아가고 글자 수가 6이 되었을 때 length == 6 조건을 통해 결과를 도출한다.

결과

제한 메모리와 제한시간과 비교해보면 괜찮을 결과를 보인다.