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

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

반응형

문제 출처 : https://www.acmicpc.net/problem/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, visited : Array){ val q : Queue> = LinkedList>() 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("

") } close() }

반응형

from http://ongveloper.tistory.com/339 by ccl(A) rewrite - 2021-11-23 17:27:16