โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Implementation

[๊ตฌํ˜„ / Kotlin] BOJ 13459 - ๊ตฌ์Šฌ ํƒˆ์ถœ

2022. 4. 4. 20:30
๋ชฉ์ฐจ
  1. ๋ฌธ์ œ
  2. ํ’€์ด ์–ธ์–ด
  3. ์ฝ”๋“œ
  4. ํ’€์ด ๋ฐฉ๋ฒ•
  5. ๊ฒฐ๊ณผ

๋ฌธ์ œ

ํ’€์ด ์–ธ์–ด

Kotlin

์ฝ”๋“œ

import java.util.*

data class Point(
    val x: Int,
    val y: Int
)

data class Points(
    val red_x: Int,
    val red_y: Int,
    val blue_x: Int,
    val blue_y: Int,
    val depth: Int
)

data class Infos(
    val x: Int,
    val y: Int,
    val cnt: Int
)

lateinit var array: Array<Array<String>>
val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, 1, -1)
var n = 0
var m = 0
var red = Point(0, 0)
var blue = Point(0, 0)

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()

    array = Array(n) { Array(m) { "" } }

    for (i in 0 until n) {
        val input = next().chunked(1)
        for (j in 0 until m) {
            array[i][j] = input[j]
        }
    }

    // ์šฐ์„  R, B์˜ ์ขŒํ‘œ๋ฅผ ์ฐพ์Œ
    find()

    // ํƒ์ƒ‰
    bfs()
}

fun find() {
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (array[i][j] == "#" || array[i][j] == ".") continue
            else if (array[i][j] == "R") red = Point(i, j)
            else if (array[i][j] == "B") blue = Point(i, j)
        }
    }
}

fun bfs() {
    var visited = Array(n) { Array(m) { Array(n) { Array(m) { 0 } } } }
    var map = LinkedList<Points>()

    map.add(Points(red.x, red.y, blue.x, blue.y, 1))
    visited[red.x][red.y][blue.x][blue.y] = 1

    while (map.isNotEmpty()) {
        val current = map.poll()

        if (current.depth > 10) break

        for (i in 0..3) {
            var redInfos = move(current.red_x, current.red_y, dx[i], dy[i])
            var blueInfos = move(current.blue_x, current.blue_y, dx[i], dy[i])

            if (array[blueInfos.x][blueInfos.y] == "O") continue
            if (array[redInfos.x][redInfos.y] == "O") {
                println(1)
                return
            }

            if (redInfos.x == blueInfos.x && redInfos.y == blueInfos.y) {
                if (redInfos.cnt > blueInfos.cnt) {
                    redInfos = Infos(redInfos.x - dx[i], redInfos.y - dy[i], redInfos.cnt)
                } else {
                    blueInfos = Infos(blueInfos.x - dx[i], blueInfos.y - dy[i], blueInfos.cnt)
                }
            }

            val points = Points(redInfos.x, redInfos.y, blueInfos.x, blueInfos.y, current.depth + 1)

            if (visited[points.red_x][points.red_y][points.blue_x][points.blue_y] == 1) continue
            visited[points.red_x][points.red_y][points.blue_x][points.blue_y] = 1

            map.add(points)
        }

    }
    println(0)
}

fun move(x: Int, y: Int, dx: Int, dy: Int): Infos {
    var nx = x
    var ny = y
    var cnt = 0

    while (array[nx + dx][ny + dy] != "#" && array[nx][ny] != "O") {
        nx += dx
        ny += dy
        cnt += 1
    }

    return Infos(nx, ny, cnt)
}

ํ’€์ด ๋ฐฉ๋ฒ•

BFS(ํ˜น์€ DFS) ๋ฅผ ํ™œ์šฉํ•œ ๊ตฌํ˜„ ๋ฌธ์ œ์ด๋‹ค. ๊ตฌ์Šฌ์ด ๋“ค์–ด์žˆ๋Š” ์ง์‚ฌ๊ฐํ˜• ๋ณด๋“œ๋ฅผ ์ด๋ฆฌ์ €๋ฆฌ ๊ตด๋ ค์„œ ๋นจ๊ฐ„ ๊ตฌ์Šฌ์„ ํŒŒ๋ž€ ๊ตฌ์Šฌ๋ณด๋‹ค ๋จผ์ € ํƒˆ์ถœ์‹œํ‚ค๋ฉด ๋œ๋‹ค. ๊ตฌํ˜„ ๋ฌธ์ œ๋‹ˆ๊นŒ ๊ทœ์น™์„ ์ฐพ์•„๋ณด์ž.

 

1. ์šฐ์„  ์ง์‚ฌ๊ฐํ˜• ๋ณด๋“œ๋Š” ๊ฐ€์žฅ์ž๋ฆฌ๊ฐ€ ๋ฒฝ์œผ๋กœ ๋‘˜๋Ÿฌ์Œ“์—ฌ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ BFS ํƒ์ƒ‰ ๊ณผ์ •์—์„œ ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚  ์ผ์ด ์—†๋‹ค.

2. ํ•˜์ง€๋งŒ ์ผ๋ฐ˜์ ์ธ BFS ๋ฌธ์ œ์™€ ๋‹ค๋ฅด๊ฒŒ ์ง์‚ฌ๊ฐํ˜• ๋ณด๋“œ๋ฅผ ํ•œ์ชฝ์œผ๋กœ ๊ธฐ์šธ์ด๋ฉด ๋ฒฝ์ด๋‚˜ ๊ตฌ๋ฉ์„ ๋งŒ๋‚  ๋–„๊นŒ์ง€ ์ง์ง„ํ•œ๋‹ค.

3. ํ˜น์€ ํ•ด๋‹น ๊ตฌ์Šฌ๋ณด๋‹ค ์•ž์„  ๊ตฌ์Šฌ์ด ์žˆ๋Š” ๊ฒฝ์šฐ ํ•ด๋‹น ๊ตฌ์Šฌ๊ณผ ํ•จ๊ป˜ ์ด๋™ํ•˜๊ฒŒ ๋œ๋‹ค.

ex) (<-์ด๋™๋ฐฉํ–ฅ-) ๋นจ๊ฐ„ ๊ตฌ์Šฌ, ํŒŒ๋ž€ ๊ตฌ์Šฌ ํ•ญ์ƒ ์ด ํ˜•ํƒœ๋ฅผ ์œ ์ง€ํ•œ๋‹ค.

 

์ด ์ •๋„์˜ ๊ทœ์น™์„ ๊ฐ€์ง€๊ณ  ์žˆ๊ณ  ์ด์ œ ๊ตฌํ˜„ํ•˜๋ฉด ๋œ๋‹ค.

 

1. ์ขŒํ‘œ์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ํšจ์œจ์ ์œผ๋กœ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด data class ๋ฅผ ์ •์˜ํ–ˆ๋‹ค. Pair ๋‚˜ Triple ์„ ์‚ฌ์šฉํ•ด๋„ ๋œ๋‹ค.

data class Point(
    val x: Int,
    val y: Int
)

data class Points(
    val red_x: Int,
    val red_y: Int,
    val blue_x: Int,
    val blue_y: Int,
    val depth: Int
)

data class Infos(
    val x: Int,
    val y: Int,
    val cnt: Int
)

 

2. ์ž…๋ ฅ ๊ฐ’์€ ๋ฐฐ์—ด์— ์ €์žฅํ•œ๋‹ค. ๋„์–ด์“ฐ๊ธฐ ๊ฐ€ ๋˜์–ด ์žˆ์ง€ ์•Š์€ ์ž…๋ ฅ ๊ฐ’์„ split ํ•ด์•ผํ•˜๋ฏ€๋กœ chunked ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ๋ถ„๋ฆฌํ•œ๋‹ค.

    array = Array(n) { Array(m) { "" } }

    for (i in 0 until n) {
        val input = next().chunked(1)
        for (j in 0 until m) {
            array[i][j] = input[j]
        }
    }

 

3. ๋นจ๊ฐ„ ๊ตฌ์Šฌ ๊ณผ ํŒŒ๋ž€ ๊ตฌ์Šฌ ์˜ ์ขŒํ‘œ๋ฅผ ํƒ์ƒ‰ํ•œ๋‹ค. ์ดˆ๊ธฐ์— ์ •์˜ํ•œ Point data class ๋ฅผ ํ™œ์šฉํ•œ๋‹ค.

fun find() {
    for (i in 0 until n) {
        for (j in 0 until m) {
            if (array[i][j] == "#" || array[i][j] == ".") continue
            else if (array[i][j] == "R") red = Point(i, j)
            else if (array[i][j] == "B") blue = Point(i, j)
        }
    }
}

 

4. ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ ๊ฐ€์ง€๊ณ  BFS ๋ฅผ ์ง„ํ–‰ํ•˜๋ฉด์„œ ๋นจ๊ฐ„ ๊ตฌ์Šฌ์˜ ํƒˆ์ถœ ์—ฌ๋ถ€๋ฅผ ํŒ๋‹จํ•˜๋ฉด ๋œ๋‹ค. ๊ทธ ์ „์— ๊ธฐ์กด BFS ๋ฌธ์ œ์™€๋Š” ๋‹ค๋ฅด๊ฒŒ ํ•œ ์นธ์”ฉ ์ด๋™ํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹Œ ๋ฒฝ์„ ๋งŒ๋‚˜๊ฑฐ๋‚˜ ๊ตฌ๋ฉ, ํ˜น์€ ๋‹ค๋ฅธ ๊ตฌ์Šฌ์„ ๋งŒ๋‚  ๋•Œ๊นŒ์ง€ ์ง์ง„ํ•˜๋Š” ํŠน์„ฑ์ด ์žˆ์œผ๋ฏ€๋กœ ์ด์™€ ๊ด€๋ จ๋œ move ํ•จ์ˆ˜๋ฅผ ๋ณ„๋„๋กœ ์ •์˜ํ–ˆ๋‹ค. cnt ๋ฅผ ์นด์šดํŠธํ•˜๋Š” ์ด์œ ๋Š” ๋นจ๊ฐ„ ๊ตฌ์Šฌ๊ณผ ํŒŒ๋ž€ ๊ตฌ์Šฌ์ด ๊ฐ™์€ ์ง€์ ์— ์กด์žฌํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ ์ด ๋•Œ ์ฒ˜๋ฆฌ๋ฅผ ํ•ด์ฃผ๊ธฐ ์œ„ํ•ด์„œ ์ด๋ฅผ ์นด์šดํŠธํ•œ๋‹ค.

fun move(x: Int, y: Int, dx: Int, dy: Int): Infos {
    var nx = x
    var ny = y
    var cnt = 0

    while (array[nx + dx][ny + dy] != "#" && array[nx][ny] != "O") {
        nx += dx
        ny += dy
        cnt += 1
    }

    return Infos(nx, ny, cnt)
}

 

5. ์ด์ œ ์ง„์งœ๋กœ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•˜๋ฉด ๋œ๋‹ค. ์ฝ”๋“œ๊ฐ€ ์ข€ ๊ธธ๋‹ค.

fun bfs() {
    var visited = Array(n) { Array(m) { Array(n) { Array(m) { 0 } } } }
    var map = LinkedList<Points>()

    map.add(Points(red.x, red.y, blue.x, blue.y, 1))
    visited[red.x][red.y][blue.x][blue.y] = 1

    while (map.isNotEmpty()) {
        // linkedList๋กœ queue ๊ตฌํ˜„
        val current = map.poll()

        // 10ํšŒ ์ด๋‚ด์— ํƒˆ์ถœํ•˜์ง€ ๋ชปํ•˜๋ฉด ์‹คํŒจ
        if (current.depth > 10) break

        // ์ƒ, ํ•˜, ์ขŒ, ์šฐ ํƒ์ƒ‰ ์ง„ํ–‰
        for (i in 0..3) {
            // ๋ฒฝ, ํƒˆ์ถœ๊ตฌ๋ฅผ ๋งŒ๋‚  ๋•Œ๊นŒ์ง€ ์ง์ง„
            var redInfos = move(current.red_x, current.red_y, dx[i], dy[i])
            var blueInfos = move(current.blue_x, current.blue_y, dx[i], dy[i])

            // ํŒŒ๋ž€ ๊ตฌ์Šฌ์ด ํƒˆ์ถœํ•˜๋ฉด ์‹คํŒจ
            if (array[blueInfos.x][blueInfos.y] == "O") continue

            // ๋นจ๊ฐ„ ๊ตฌ์Šฌ์ด ํƒˆ์ถœํ•˜๋ฉด ์„ฑ๊ณต
            if (array[redInfos.x][redInfos.y] == "O") {
                println(1)
                return
            }

            // ๋นจ๊ฐ„ ๊ตฌ์Šฌ๊ณผ ํŒŒ๋ž€ ๊ตฌ์Šฌ์ด ๊ฐ™์€ ์œ„์น˜์— ์กด์žฌํ•˜๋ฉด
            if (redInfos.x == blueInfos.x && redInfos.y == blueInfos.y) {
                // ์ด๋™ ๊ฑฐ๋ฆฌ๋ฅผ ๋น„๊ตํ•˜์—ฌ ๋” ๋ฉ€๋ฆฌ ์ด๋™ํ•œ ๊ตฌ์Šฌ์„ ํ•œ ์นธ ๋’ค๋กœ ์ด๋™ํ•œ๋‹ค.
                if (redInfos.cnt > blueInfos.cnt) {
                    redInfos = Infos(redInfos.x - dx[i], redInfos.y - dy[i], redInfos.cnt)
                } else {
                    blueInfos = Infos(blueInfos.x - dx[i], blueInfos.y - dy[i], blueInfos.cnt)
                }
            }

            // ์ด๋™ํ•œ ์ขŒํ‘œ์™€ depth++๋ฅผ ์ €์žฅ
            val points = Points(redInfos.x, redInfos.y, blueInfos.x, blueInfos.y, current.depth + 1)

            // ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์ขŒํ‘œ์ด๋ฉด continue
            if (visited[points.red_x][points.red_y][points.blue_x][points.blue_y] == 1) continue

            // ํ•ด๋‹น ์ขŒํ‘œ ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ
            visited[points.red_x][points.red_y][points.blue_x][points.blue_y] = 1

            // ์ƒˆ๋กœ์šด ์ขŒํ‘œ๋ฅผ queue์— ์‚ฝ์ž…
            map.add(points)
        }

    }
    println(0)
}

๊ฒฐ๊ณผ

10ํšŒ ์ด๋‚ด ์— ํƒˆ์ถœํ•˜์ง€ ๋ชปํ•œ ๊ฒฝ์šฐ ์ด๋Š” ์‹คํŒจ๋กœ ๊ฐ„์ฃผํ•˜๋Š”๋ฐ ์ด์— ๋Œ€ํ•œ ์กฐ๊ฑด์‹์„ ์ž˜๋ชป ์ž‘์„ฑํ•ด์„œ ๊ณ„์† ์‹คํŒจํ–ˆ๋‹ค. ์ดˆ๊ธฐ์—๋Š” ์ƒ, ํ•˜, ์ขŒ, ์šฐ ์— ๋Œ€ํ•œ ํƒ์ƒ‰์„ ์™„๋ฃŒํ•œ ๊ฒฝ์šฐ์— depth++ ๋ฅผ ์ง„ํ–‰ํ–ˆ๋Š”๋ฐ ์ด๋Š” ์ž˜๋ชป๋œ ๋ฐฉ๋ฒ•์ด์—ˆ๋‹ค. ์ด๋ฅผ depth๊นŒ์ง€ Points ๊ฐ์ฒด์— ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ํ•ด๊ฒฐํ–ˆ๋‹ค.

์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ > Implementation' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] 124 ๋‚˜๋ผ์˜ ์ˆซ์ž  (0) 2022.06.09
[๊ตฌํ˜„ / Kotlin] 2022 SK ICT Family ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ ์ฑŒ๋ฆฐ์ง€ - 2๋ฒˆ  (0) 2022.03.12
  1. ๋ฌธ์ œ
  2. ํ’€์ด ์–ธ์–ด
  3. ์ฝ”๋“œ
  4. ํ’€์ด ๋ฐฉ๋ฒ•
  5. ๊ฒฐ๊ณผ
'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Implementation' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] 124 ๋‚˜๋ผ์˜ ์ˆซ์ž
  • [๊ตฌํ˜„ / Kotlin] 2022 SK ICT Family ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ ์ฑŒ๋ฆฐ์ง€ - 2๋ฒˆ
kodo_o
kodo_o
iOS ๊ฟ€์žผ!
๐ŸŽ๐ŸiOS ๊ฟ€์žผ!
kodo_o
๐ŸŽ๐Ÿ
kodo_o
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (149)
    • ๐Ÿ”จ ํ”„๋กœ์ ํŠธ (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • ๐Ÿ’ป ๊ฐœ๋ฐœ (63)
      • iOS (30)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • ์˜ค๋Š˜์˜ ์‚ฝ์งˆ (7)
      • ์—๋Ÿฌ์™€์˜ ๋™์นจ (1)
    • โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • ๐Ÿ“š CS (6)
      • Operating System (6)
    • โ›น๏ธ ๋ผ์ดํ”„ (30)
      • 2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (12)
      • 2021 ์—ฌ๋ฆ„๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (6)
      • ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ (1)
      • ํšŒ๊ณ  (10)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ๊นƒํ—ˆ๋ธŒ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.
kodo_o
[๊ตฌํ˜„ / Kotlin] BOJ 13459 - ๊ตฌ์Šฌ ํƒˆ์ถœ
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.