[BOJ] 2178번 : 미로 탐색

문제 보기

BFS, 다차원 배열에서의 거리 측정 문제

kotlin

visit 배열을 사용하지 않고 거리를 담은 dist 배열만 이용

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    val (n, m) = nextInt() to nextInt()
    val (dx, dy) = intArrayOf(1, 0, -1, 0) to intArrayOf(0, 1, 0, -1)
    val maze = Array(n) { IntArray(m) }
    val dist = Array(n) { IntArray(m) { -1 } }

    for (i in 0 until n) { // 각각의 수들은 '붙어서' 입력으로 주어진다.
        val line = next()
        for (j in 0 until m) {
            maze[i][j] = line[j] - '0'
        }
    }

    val queue: Queue<Pair<Int, Int>> = LinkedList()
    queue.offer(0 to 0)
    dist[0][0] = 0

    while (queue.isNotEmpty()) {
        val (curX, curY) = queue.poll()

        for (dir in 0 until 4) {
            val (nx, ny) = (curX + dx[dir]) to (curY + dy[dir])

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
            if (dist[nx][ny] >= 0 || maze[nx][ny] != 1) continue

            dist[nx][ny] = dist[curX][curY] + 1
            queue.offer(nx to ny)
        }
    }

    print(dist[n - 1][m - 1] + 1) // 지나는 칸 수를 출력이므로 + 1
}

Triple의 third 값에 거리 추가

import java.util.*

var n = 0
var m = 0
var dx = intArrayOf(1, 0, -1, 0)
var dy = intArrayOf(0, 1, 0, -1)
lateinit var maze: Array<IntArray>
lateinit var visit: Array<BooleanArray>

fun main() {
    init()
    println(bfs())
}

fun bfs() : Int {
    val queue: Queue<Triple<Int, Int, Int>> = LinkedList()
    queue.offer(Triple(0, 0, 1))
    visit[0][0] = true

    while (queue.isNotEmpty()) {
        val (curX, curY, count) = queue.poll()
        for (dir in 0 until 4) {
            val (nx, ny) = curX + dx[dir] to curY + dy[dir]

            if (nx == n - 1 && ny == m - 1) {
                return count + 1
            }

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue
            if (visit[nx][ny] || maze[nx][ny] == 0) continue

            visit[nx][ny] = true
            queue.add(Triple(nx, ny, count + 1))
        }
    }
    return 0
}

fun init() = with(Scanner(System.`in`)) {
    n = nextInt()
    m = nextInt()
    maze = Array(n) { IntArray(m) }
    visit = Array(n) { BooleanArray(m) }

    for (i in 0 until n) {
        val line = next()
        for (j in 0 until m) {
            maze[i][j] = Character.getNumericValue(line[j]) // line[j] - '0' 와 동일
        }
    }
}