[BOJ] 14940 쉬운 최단거리 - JAVA

1. 문제

14940번: 쉬운 최단거리

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

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

---

2. 풀이

입력

int[][] 배열에 2나 0이면 0(시작지점이거나 도달할 수 없는 경우)을 저장하고 1이면 -1을 저장한다.

2라면 queue에 넣어서 bfs탐색을 시작할 수 있도록 한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] answer = new int[N][M];
Queue<int[]> queue = new ArrayDeque<>();
for(int i=0;i<N;i++){
   st = new StringTokenizer(in.readLine());
   for(int j=0;j<M;j++){
      int num = Integer.parseInt(st.nextToken());
      if(num!=1) answer[i][j] = 0;
      else answer[i][j] = -1;
      if(num==2) queue.offer(new int[]{i,j});
   }
}

 

탐색

큐의 맨 앞 순서를 뽑아서 사방으로 갈 수 있는지 체크한다.

갈 수 있다면 answer[ni][nj]에 새로운 값을 저장하고 큐에 위치를 넣는다.

int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};
int[] node;
int ni,nj;
while(!queue.isEmpty()){
   node = queue.poll();
   for(int[] d:deltas){
      ni = node[0]+d[0];
      nj = node[1]+d[1];
      if(ni<0||nj<0||ni>=N||nj>=M||answer[ni][nj]!=-1) continue;
      answer[ni][nj] = answer[node[0]][node[1]]+1;
      queue.offer(new int[]{ni,nj});
   }
}

 

출력

StringBuilder를 생성해서 answer의 요소를 하나씩 더한다.

StringBuilder sb = new StringBuilder();
for(int i=0;i<N;i++){
   for(int j=0;j<M;j++){
      sb.append(answer[i][j]).append(' ');
   }
   sb.append('\n');
}

System.out.print(sb);

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_14940_쉬운최단거리 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      int[][] answer = new int[N][M];
      Queue<int[]> queue = new ArrayDeque<>();
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         for(int j=0;j<M;j++){
            int num = Integer.parseInt(st.nextToken());
            if(num!=1) answer[i][j] = 0;
            else answer[i][j] = -1;
            if(num==2) queue.offer(new int[]{i,j});
         }
      }

      int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};
      int[] node;
      int ni,nj;
      while(!queue.isEmpty()){
         node = queue.poll();
         for(int[] d:deltas){
            ni = node[0]+d[0];
            nj = node[1]+d[1];
            if(ni<0||nj<0||ni>=N||nj>=M||answer[ni][nj]!=-1) continue;
            answer[ni][nj] = answer[node[0]][node[1]]+1;
            queue.offer(new int[]{ni,nj});
         }
      }

      StringBuilder sb = new StringBuilder();
      for(int i=0;i<N;i++){
         for(int j=0;j<M;j++){
            sb.append(answer[i][j]).append(' ');
         }
         sb.append('\n');
      }

      System.out.print(sb);
   }
}

---

3. 결과