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

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

14940번: 쉬운 최단거리

문제

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

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

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

bfs 문제이다.

그래프를 입력받으면서, 시작점이 될 2 부분을 미리 저장해놓자.

2를 시작점이라 표현하는 이유는, 각 점에서 2로 가는 거리는 반대로, 2에서 각 점으로 가는 거리와 같기 때문에,

2에서 시작하여 모든 점에 대한 거리를 구하면 되기 때문이다.

 

따라서 시작점부터 bfs를 돌려서 모든 점에 대한 거리를 graph에 저장하면 되고,

애초에 갈 수 없는 땅(0)인 부분은 visited true처리를 해주어서 도달할 수 없는 땅과 구분을 해주자.

 

코드

import java.util.*

//n은 행 m은 열
//2<=n,m<=1000
//0방문 불가,1은 방문 가능
//도달할 수 없는 경우 -1 출력, 원래갈 수 없는 땅은 0 출력

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

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

    while(q.isNotEmpty()){
        val (r,c) = q.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(graph[nR][nC]==0){
              visited[nR][nC]=true
                continue
            }
            graph[nR][nC] = graph[r][c]+1
            visited[nR][nC] =true
            q.add(Pair(nR,nC))
        }
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br =System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val visited = Array(n){BooleanArray(m)}

    var sr =-1
    var sc =-1
    val graph = 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, graph,visited)

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