[백준] 16924번. 십자가 찾기(Kotlin)

문제

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

---

풀이(18분)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

// 입력 크기
var N = 0
var M = 0

// 지도 및 방문 가능한 위치 배열 (입력 후 초기화)
lateinit var map: Array<Array<Boolean>>
lateinit var possible: Array<Array<Boolean>>

// 방향 벡터 (상, 하, 좌, 우)
val dX = arrayOf(-1, 1, 0, 0)
val dY = arrayOf(0, 0, -1, 1)

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

    // N, M 입력
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    // 배열 초기화
    map = Array(N) { Array(M) { false } }
    possible = Array(N) { Array(M) { false } }

    // 지도 입력 처리 ('*'이면 true)
    repeat(N) { i ->
        val line = br.readLine()
        repeat(M) { j ->
            map[i][j] = line[j] == '*'
        }
    }

    var cnt = 0 // 결과 개수 카운트

    // 전체 맵 탐색
    repeat(N) { i ->
        repeat(M) { j ->
            if (map[i][j]) {
                var depth = 1

                // 십자가 형태 확인
                if (!dfs(i, j, depth)) {
                    depth = 0
                } else {
                    // 가능한 깊이까지 확장
                    while (dfs(i, j, depth)) {
                        depth++
                        for (k in 0..3) {
                            val nX = i + dX[k] * depth
                            val nY = j + dY[k] * depth
                            possible[nX][nY] = true
                        }
                    }
                }

                // 십자가 중심이 유효한 경우 결과 저장
                if (depth != 0) {
                    sb.append("$i $j $depth").append("\n")
                    possible[i][j] = true
                    cnt++
                }
            }
        }
    }
    
    // 실패 처리
    repeat(N) { i ->
        repeat(M) { j ->
            if (map[i][j]) {
                if (!possible[i][j]) {
                    println(-1)
                    return
                }
            }
        }
    }

    // 출력
    println(cnt)
    println(sb)
}

// 깊이(depth)만큼 십자가 형태가 가능한지 확인
fun dfs(sX: Int, sY: Int, depth: Int): Boolean {
    for (i in 0..3) {
        val nX = sX + dX[i] * depth
        val nY = sY + dY[i] * depth
        if (!isBound(nX, nY)) return false
        if (!map[nX][nY]) return false
    }
    return true
}

// 배열 경계 체크
fun isBound(x: Int, y: Int): Boolean = x in 0 until N && y in 0 until M

---

문제 풀이 전략

 

1. 입력 처리
   • 지도 크기 N, M을 입력받는다.
   • map[i][j]에 '*' 여부(true/false)를 저장한다.
2. 십자가 중심 탐색
   • 모든 칸 (i, j)를 순회하면서,
     그 칸이 '*'이면 중심 후보로 간주한다.
   • 상하좌우 방향으로 같은 거리(depth)만큼 '*'가 존재하는지 확인한다.
   • 가능한 한 최대 깊이까지 확장하면서 십자가의 크기를 계산한다.
3. 유효한 십자가 저장
   • 십자가가 유효하면 결과 리스트(StringBuilder)에 중심 좌표와 깊이를 저장한다.
   • 해당 중심 및 팔 부분 좌표를 possible[i][j] = true로 표시한다.
4. 출력
   • 전체 십자가 개수(cnt)와 각 십자가의 (i, j, depth)를 출력한다.