백준 [자바 java] 14904 : 쉬운 최단거리

https://www.acmicpc.net/problem/14940

지도가 주어지고 각 위치마다 목표지점까지 얼마나 걸리는지를 출력하는 문제이다.

우선 bfs를 이용한 문제라는건 인식했다!

그래서 처음에는 각 계층마다 cnt값을 넣어주는 방식으로 답을 정의했는데 생각해보니까 이 문제는 각 위치마다의 값을 저장하는 문제이기 때문에 그냥 그 시점에 해당 노드 값에 1을 더한 값을 넣어주면 되는 것이었다.

 

핵심 개념

for(int i = 0;i<n;i++){
  st = new StringTokenizer(br.readLine());
  for(int j = 0;j<m;j++){
    arr[i][j] = Integer.parseInt(st.nextToken());
    if(arr[i][j] == 2){
      q.offer(new xy(i,j));
      vis[i][j] = 1;
    }
    if(arr[i][j] == 0){
      vis[i][j] = 1;
    }
  }
}

우선 입력을 받다가 2를 만나면 여기가 도착지점이므로 이 노드를 큐에 넣는다.

 

int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};

  while(q.size() != 0){
    xy now = q.poll();
    for(int k = 0;k<4;k++){
      int nx = now.x + dx[k];
      int ny = now.y + dy[k];
      if(nx >= 0 && nx <n && ny >= 0 && ny<m && vis[nx][ny] == 0){
        q.offer(new xy(nx,ny));
        ans[nx][ny] = ans[now.x][now.y] +1;
        vis[nx][ny] = 1;
      }
    }
  }

이 문제에서는 위아래 양옆을 사용해서 dx,dy테크닉을 사용하였다.

큐에서 노드를 꺼낸 후 해당 노드의 사방을 확인하고 다시 큐에 넣는다. 큐에 넣을 때 ans(최단거리)값은 지금 꺼낸 노드 값 +1을 해서 넣어주었다.

 

 

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
    if (arr[i][j] == 0) {
      sb.append("0 ");
    } else if (vis[i][j] == 0) {
      sb.append("-1 ");
    } else {
      sb.append(ans[i][j]).append(" ");
    }
  }
  sb.append("\n");
}

이 문제의 핵심이다.

아니 분명 이거보다 최적화할 순 없는데 왜 시간초과가 나나 했더니

System.out.println을 사용해서였다.

이 문제는 출력해야할 것이 굉장히 많은데 이럴 때 자바에서는 stringBuilder을 사용해야한다.

이렇게 해야 훨씬 효율적이다!

 

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

class xy{
  int x;
  int y;
  public xy(int x, int y){
    this.x = x;
    this.y = y;
  }
}

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    int[][] arr = new int[n][m];
    int[][] ans = new int[n][m];
    int[][] vis = new int[n][m];

    Queue<xy> q = new LinkedList<>();

    for(int i = 0;i<n;i++){
      st = new StringTokenizer(br.readLine());
      for(int j = 0;j<m;j++){
        arr[i][j] = Integer.parseInt(st.nextToken());
        if(arr[i][j] == 2){
          q.offer(new xy(i,j));
          vis[i][j] = 1;
        }
        if(arr[i][j] == 0){
          vis[i][j] = 1;
        }
      }
    }

    int[] dx = {0,1,0,-1};
    int[] dy = {1,0,-1,0};

      while(q.size() != 0){
        xy now = q.poll();
        for(int k = 0;k<4;k++){
          int nx = now.x + dx[k];
          int ny = now.y + dy[k];
          if(nx >= 0 && nx <n && ny >= 0 && ny<m && vis[nx][ny] == 0){
            q.offer(new xy(nx,ny));
            ans[nx][ny] = ans[now.x][now.y] +1;
            vis[nx][ny] = 1;
          }
        }
      }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (arr[i][j] == 0) {
          sb.append("0 ");
        } else if (vis[i][j] == 0) {
          sb.append("-1 ");
        } else {
          sb.append(ans[i][j]).append(" ");
        }
      }
      sb.append("\n");
    }

    System.out.print(sb);

  }
}

 

 

전체 코드이다.