[종만북] 6.2 재귀호출과 완전탐색[보글게임]

PS를 풀다보면서 재귀와 완전탐색에 대한 사고력이 부족하다고 느껴서 종만북을 사게 되었다.

앞부분에 대한 내용은 PS를 어떻게 잘 풀지에 대한 사고력의 전환과 관련된 내용인데

내 레벨이 부족해서 크게 와닿지 않는다.

그래서 앞부분 조금 읽다가 가장 빠르게 느낄수 있는 6장 부터 시작했다.

 

6장 첫 번째 문제는 보글게임이라는 문제인데.

 

알파벳 배열이 입력으로 주어지고 해당 배열에서 원하고자 하는 단어를 맞출수 있는지를

재귀적으로 푸는 문제이다.

 

예를 들면 

 

'U', 'R', 'L', 'P', 'M'
'X', 'P', 'R', 'E', 'T'
'G', 'I', 'A', 'E', 'T'
'X', 'T', 'N', 'Z', 'Y'
'X', 'O', 'Q', 'R', 'S'

이라는 인풋이 들어올때 PRETTY라는 글자가 맞춰질 수 있다면 true 아니면 false를 출력하는 것이다.

기존에 내가 코딩하던 방식으로 짰을 때

파라미터로 넘어가는 6개로 변수들이 많았다.

 

근데 종만북에 해결책으로 제시된 내용을 보면 파라미터가 3개 밖에 안들어간다.

이런 차이점에서 배울점이 많은 부분인거 같다.

 

코드를 비교해보면 알수 있다.

 

기존 내 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.ArrayList

lateinit var arr: Array<Array<Char>>


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    arr = arrayOf(
        arrayOf('U', 'R', 'L', 'P', 'M'),
        arrayOf('X', 'P', 'R', 'E', 'T'),
        arrayOf('G', 'I', 'A', 'E', 'T'),
        arrayOf('X', 'T', 'N', 'Z', 'Y'),
        arrayOf('X', 'O', 'Q', 'R', 'S')
    )
    val word = "PRETTY"
    for(i in 0..arr.size-1){
        for(j in 0..arr.size-1){
            if(arr[i][j]==word[0]){
                val res = dfs(i, j,1,""+word[0],arr.size,word)
                if(res) {
                    println(res)
                    return
                }
            }
        }
    }
    println("false")


}

fun dfs(x: Int, y: Int, index: Int, str: String, n: Int, word: String): Boolean {
    val dx = arrayOf(-1, 1, 0, 0, 1, -1, 1, -1)
    val dy = arrayOf(0, 0, -1, 1, -1, -1, 1, 1)
    if (str == word) return true
    for (i in 0..dx.size - 1) {
        if (x + dx[i] > -1 && x + dx[i] < n && y + dy[i] > -1 && y + dy[i] < n) {
            val mx = x + dx[i]
            val my = y + dy[i]
            if (arr[mx][my] == word[index]) {
                val res = dfs(mx, my, index + 1, str + arr[mx][my], n, word)
                if(res) return true
            }
        }
    }
    return false
}

 

 

종만북을 보고난 후 내 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.ArrayList

lateinit var arr: Array<Array<Char>>
var N = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    arr = arrayOf(
        arrayOf('U', 'R', 'L', 'P', 'M'),
        arrayOf('X', 'P', 'R', 'E', 'T'),
        arrayOf('G', 'I', 'A', 'E', 'T'),
        arrayOf('X', 'T', 'N', 'Z', 'Y'),
        arrayOf('X', 'O', 'Q', 'R', 'S')
    )
    N = arr.size
    val word = "PRETTY"
    for(i in 0..arr.size-1){
        for(j in 0..arr.size-1){
            if(arr[i][j]==word[0]){
                val res = dfs(i, j, word)
                if(res) {
                    println(res)
                    return
                }
            }
        }
    }
    println("false")


}

fun dfs(x: Int, y: Int, word: String): Boolean {
    val dx = arrayOf(-1, 1, 0, 0, 1, -1, 1, -1)
    val dy = arrayOf(0, 0, -1, 1, -1, -1, 1, 1)
    if(!inRange(x, y)) return false

    if(arr[x][y]!=word[0]) return false

    if (word.length == 1) return true

    for (i in 0..dx.size - 1) {
        val mx = x + dx[i]
        val my = y + dy[i]
        val res = dfs(mx, my, word.substring(1))
        if(res) return true
    }
    return false
}

fun inRange(x: Int, y: Int): Boolean{
    if (x > -1 && x < N && y > -1 && y < N) return true

    return false
}

 

혹시나 위 내용이 저작권법에 위반된다면 바로 내리겠습니다.

감사합니다.