[백준][KOTLIN][16929] Two Dots

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

16929번: Two Dots

문제 풀이

1. 싸이클에 대한 조건을 확인하여 DFS 를 이용한다.

2. DFS 탈출 조건은 싸이클을 만족할 때 탈출되도록 하고 아니면 전체 탐색 한다.

3. 싸이클이 되기 위해서 depth 가 4보다 크거나 같고 시작 (x, y) 와 새롭게 탐색되는 점이 같은 지 확인 한다.

코드

import java.io.*

private var result = "No"

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val game = Array(N) {
        CharArray(M) {
            'A'
        }
    }

    repeat(N) {
        game[it] = br.readLine().toCharArray()
    }

    var startChar = '0'
    var findCycle = false

    for (i in 0 until N) {
        for (j in 0 until M) {
            val visit = Array(N) {
                BooleanArray(M) {
                    false
                }
            }

            startChar = game[i][j]
            //println("startChar : $startChar")
            visit[i][j] = true
            dfs(N, M, game, visit, startChar, i, j, i, j, 1)

            if (result == "Yes") {
                findCycle = true
                break
            }
        }

        if (findCycle) break
    }

    println(result)
}

private fun dfs(N: Int, M: Int, game: Array<CharArray>, visit: Array<BooleanArray>, ch: Char, x: Int, y: Int, startX: Int, startY: Int, depth: Int) {
    // 상, 하, 좌, 우 탐색
    val changeX = intArrayOf(-1, 1, 0, 0)
    val changeY = intArrayOf(0, 0, -1, 1)


    for (i in 0..3) {
        val newX = x + changeX[i]
        val newY = y + changeY[i]
        //println("startX: $startX, startY: $startY, x: $x, y: $y, newX: $newX, newY: $newY, depth: $depth")

        if (newX == startX && newY == startY && depth >= 4) {
            result = "Yes"
            break
        }

        //범위 밖 영역
        if ((newX < 0 || newX >= N) || (newY < 0 || newY >= M)) continue
        //입력으로 들어온 ch 와 다른 색
        if (ch != game[newX][newY]) continue
        //이미 방문한 곳
        if (visit[newX][newY]) continue

        visit[newX][newY] = true
        dfs(N, M, game, visit, ch, newX, newY, startX, startY, depth + 1)
    }
}