[BFS] - S1_14940_쉬운 최단거리

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

14940번: 쉬운 최단거리

 

 

 

📌- 풀이

1. 입력받을 때 0이면 0, 1이면 -1, 2이면 0을 배열에 저장하고 2일 경우엔 해당 좌표를 Queue에 add
2. 해당 좌표를 시작으로 4방향을 체크하면서 배열의 좌표값이 -1일 경우만 BFS를 하면서 해당 값에 depth를 추가하여 하나씩 거쳐갈 때마다 depth + 1 로 거리를 체크함

 

해당 문제는 별로 어렵지 않은 BFS 문제였는데, 시간이 처음엔 2448ms 정도가 나오길래 너무 비효율적으로 짰나 싶어서 다른 사람들의 코드를 보니까 로직 자체에는 별반 차이가 없어서 뭔가 싶었음

 

설마하고 이때까지 선언만 해놓고 잘 사용은 안하고 있었던 StringBuilder로 출력을 하니까 속도가 거의 4배 차이가 나고 메모리도 거의 반토막 수준까지 떨어짐

 

 

 

앞으로 짧은 출력을 제외하고 조금 출력이 길어진다 싶으면 무조건 StringBuilder를 써야할듯

 

🔥 - Java 코드

 

package BFS.S1_14940_쉬운최단거리;

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


class Locate{
    int x;
    int y;
    int depth;
    Locate(int x,int y,int depth){
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
}
public class Main {
        public static int N,M;
        public static int[][] arr;
        public static Queue<Locate> queue;
    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        queue = new LinkedList<>();
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                int n = Integer.parseInt(st.nextToken());
                if(n == 2){
                    queue.add(new Locate(i,j,0));
                    arr[i][j] = 0;
                }else if(n == 0){
                    arr[i][j] = 0;
                }else{
                    arr[i][j] = -1;
                }

            }
        }

        BFS();


        for(int[] i : arr){
            for(int j: i){
                sb.append(j).append(" ");

            }
            sb.append("\n");
        }

        System.out.println(sb);

    }

    public static void BFS(){
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};


        while(!queue.isEmpty()){
            Locate temp = queue.poll();
            int x = temp.x;
            int y = temp.y;
            int depth = temp.depth;
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(0<= nx && nx<N && 0<=ny && ny<M && arr[nx][ny] == -1){
                    arr[nx][ny] = depth+1;
                    queue.add(new Locate(nx,ny,depth+1));
                }
            }

        }
    }

}