백준 16929번 Two Dots Kotlin

: ) YOUNG·어제
1

알고리즘

목록 보기
439/441
post-thumbnail

백준 16929번 Two Dots Kotlin

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

문제



생각하기


  • 그래프 문제

  • 사이클 찾기 문제



동작





결과


코드


Kotlin


import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var M = 0
private var flag = false
private lateinit var arr: Array<CharArray>
private lateinit var isVisited: Array<BooleanArray>

private val dirX = intArrayOf(-1, 0, 1, 0)
private val dirY = intArrayOf(0, 1, 0, -1)

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    for (i in 0 until N) {
        for (j in 0 until M) {
            if (isVisited[i][j]) continue

            if (DFS(i, j, i, j, arr[i][j])) {
                sb.append("Yes")
                return sb.toString()
            }
        }
    }

    sb.append("No")
    return sb.toString()
} // End of solve()

private fun DFS(x: Int, y: Int, preX: Int, preY: Int, color: Char): Boolean {
    if (isVisited[x][y]) return true
    isVisited[x][y] = true

    for (i in 0 until 4) {
        val nX = x + dirX[i]
        val nY = y + dirY[i]

        if (!isAbleCheck(nX, nY, color)) continue
        if (nX == preX && nY == preY) continue

        if (DFS(nX, nY, x, y, color)) {
            return true
        }
    }

    return false
} // End of DFS()

private fun isAbleCheck(x: Int, y: Int, color: Char): Boolean {
    return x in 0 until N && y in 0 until M && arr[x][y] == color
} // End of isAbleCheck()

private fun input() {
    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    arr = Array(N) {
        br.readLine().toCharArray()
    }
    isVisited = Array(N) { BooleanArray(M) }
} // End of input()


0개의 댓글