14940번: 쉬운 최단거리

문제 출처 : https://www.acmicpc.net/problem/14940

 

언어 : Kotlin

 

문제 설명 :

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

• 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
• 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.
• 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

 

입출력 예 :

입력

출력

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

다른 사람의 풀이 : 

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

val dir = arrayOf(arrayOf(0, 1), arrayOf(1, 0), arrayOf(0, -1), arrayOf(-1, 0))

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    val visited = Array(n) { BooleanArray(m) { false } }
    var sr = -1
    var sc = -1


    val tree = Array(n) { x ->
        val st = StringTokenizer(br.readLine())
        
        IntArray(m) { y ->
            val node = st.nextToken().toInt()
            if (node == 2) { sr = x; sc = y }
            node
        }
    }

    bfs(sr, sc, n, m, tree, visited)

    for (r in 0 until n) {
        for (c in 0 until m) {
            if (tree[r][c] == 0) { bw.write("0 "); continue }
            if (visited[r][c]) bw.write("${tree[r][c]} ")
            else bw.write("-1 ")
        }
        bw.write("\n")
    }
    bw.flush()
    bw.close()
}

fun bfs(i: Int, j: Int, n: Int, m: Int, tree: Array<IntArray>, visited: Array<BooleanArray>) {
    val queue: Queue<Pair<Int, Int>> = LinkedList<Pair<Int, Int>>()
    queue.add(Pair(i, j))
    tree[i][j] = 0
    visited[i][j] = true

    while (queue.isNotEmpty()) {
        val (r, c) = queue.poll()

        for (i in 0 until 4) {
            val nR = r + dir[i][0]
            val nC = c + dir[i][1]

            if (nR < 0 || nR >= n || nC < 0 || nC >= m) continue
            if (visited[nR][nC]) continue
            if (tree[nR][nC] == 0 ) { visited[nR][nC] = true; continue }

            tree[nR][nC] = tree[r][c] + 1
            visited[nR][nC] = true
            queue.add(Pair(nR, nC))
        }
    }
}

 

자세한 풀이 : https://ongveloper.tistory.com/339

백준 14940 쉬운 최단거리 Kotlin (bfs)

 

 

bfs 문제인 것을 깨닫고 풀려고 노력했으나 막혀서 다른 사람의 풀이를 참고하였다.

그래프를 그리고 방향이 나오는 문제에 대해서 상당히 약한 것 같다