Today I Learned

오늘은 코틀린 코테 공부!

쉬운 최단거리

백준 14940번 https://www.acmicpc.net/problem/14940

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 24334 9633 7848 37.184%
문제
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.
각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

• 입력
  15 15
  2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
  1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
  1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

• 출력
  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
  4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
  5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
  6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
  7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
  8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
  11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
  12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
  13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
  14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

풀이 과정

• 이 문제는 큐를 이용한 BFS로 문제를 풀었다.

1. 우선 입력을 받을 변수와 배열을 선언한다. 방문 여부를 표시하는 boolean배열도 선언해둔다. 목표지점의 좌표는 x,y로 찾아낸다.

2. search 함수를 private으로 선언해둔다. 이 함수는 bfs를 이용해 목표 지점으로부터의 최단 거리를 계산한다. 각 칸에 도달하는데 걸리는 거리를 result 배열에 저장한다. 방문한 칸은 visited에 표시하고 갈 수 없는 칸은 제외한다. 결과적으로 result에는 각 칸까지의 최단 거리가 저장된다.

3. 큐가 비어있지 않은 동안에는 계속 반복문을 실행한다. 큐에서 좌표를 하나씩 꺼내서 상하좌우로 인접한 칸을 확인한다. 각 칸이 유효한지, 방문한 적이 있는지 확인 후 갈 수 있는 칸이면 이동해 거리를 update하고 큐에 추가한다.

4. 최종적으로 result 배열을 순회하면서 각 칸까지의 최단 거리를 출력하고 해당 칸에 도착하지 못하면 -1을 출력한다.

Kotlin 코드

import java.util.*

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }

    val arr = Array(n) { readln().split(" ").map { it.toInt() }.toIntArray() }
    val result = Array(n) { IntArray(m) }
    val visited = Array(n) { BooleanArray(m) }

    var x = 0
    var y = 0
    for (i in arr.indices) {
        for (j in arr[i].indices) {
            if (arr[i][j] == 2) {
                x = i
                y = j
            } else if (arr[i][j] == 0) visited[i][j] = true
        }
    }
    search(x, y, arr, visited, result, n, m)

    for (i in result.indices) {
        for (j in result[i].indices) {
            if (!visited[i][j]) result[i][j] = -1
            print("${result[i][j]} ")
        }
        println()
    }
}

private fun search(x: Int, y: Int, arr: Array<IntArray>, visited: Array<BooleanArray>, result: Array<IntArray>, n: Int, m: Int) {
    val queue: Queue<Pair<Int, Int>> = LinkedList()
    queue.add(x to y)
    visited[x][y] = true

    val dx = intArrayOf(-1, 1, 0, 0)
    val dy = intArrayOf(0, 0, -1, 1)

    while (queue.isNotEmpty()) {
        val (tempX, tempY) = queue.poll()
        for (i in 0 until 4) {
            val a = tempX + dx[i]
            val b = tempY + dy[i]
            if (a in 0 until n && b in 0 until m) {
                if (!visited[a][b] && arr[a][b] == 1) {
                    visited[a][b] = true
                    result[a][b] = result[tempX][tempY] + 1
                    queue.add(a to b)
                }
            }
        }
    }
}