[백준] 14940 쉬운 최단거리 : 실버 1 (java) - BFS

✔️문제

 

✔️ 풀이 코드

이 문제는 BFS 알고리즘을 사용해 2차원 배열에서 시작점으로부터의 최단 거리를 구하는 문제이다.

Point 클래스를 정의해서 각각의 위치와 출발점으로 부터의 거리를 함께 저장했다.

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main{
    static int n, m;
    static int[][] arr;
    static int[] dx = {-1,0,0,1};
    static int[] dy = {0,1,-1,0};
    static int[][] visited;
    static int start_i, start_j;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        visited = new int[n][m];

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++){
                int num = Integer.parseInt(st.nextToken());
                arr[i][j] = num;
                if(num == 0) visited[i][j] = 0;
                else visited[i][j] = -1;
                if(num == 2) {
                    start_i = i;
                    start_j = j;
                }
            }
        }

        bfs();

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m ; j++){
                sb.append(visited[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
    public static void bfs(){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(start_i,start_j,0));
        visited[start_i][start_j] = 0;
        while(!q.isEmpty()){
            Point current = q.poll();

            for(int i = 0; i<4; i++){
                int next_i = current.i + dx[i];
                int next_j = current.j + dy[i];

                if(next_i <0 || next_i >= n || next_j <0 || next_j >= m)
                    continue;
                if(arr[next_i][next_j] == 0)
                    continue;
                if(visited[next_i][next_j] != -1)
                    continue;

                q.add(new Point(next_i, next_j, current.cnt+1));
                visited[next_i][next_j] = current.cnt+1;
            }
        }
    }

    public static class Point{
        int i, j, cnt;
        public Point(int i, int j, int cnt){
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
    }
}

 

 

✔️ 시간 개선

로직 자체는 전형적인 BFS로, 특별히 비효율적인 부분은 없어 보였다.

하지만 제출 결과는 메모리 73612KB, 시간 1792ms로 생각보다 많은 리소스를 사용하고 있었다.

다른 사람들의 코드와 비교해도 알고리즘 구조 자체는 동일했으며, 탐색 순서나 큐의 사용 방식에서도 특별한 차이는 없었다.
차이를 보인 유일한 부분은 "출력 방식"이었다.

Java에서는 System.out.print()과 System.out.println()을 반복적으로 호출하면, 내부적으로 많은 I/O 작업이 발생해 시간과 메모리를 동시에 잡아먹는다.
특히 2차원 배열을 한 줄씩 출력할 때 이 문제가 두드러진다.

• System.out.print()는 한 번 호출될 때마다 JVM → OS → 콘솔까지 I/O 작업이 발생
• 이는 매우 느릴 뿐 아니라, 내부 버퍼 처리로 인해 메모리 낭비도 발생

✔️ 1792ms : 표준 입출력 사용

for(int i = 0; i < n; i++){
    for(int j = 0; j < m ; j++){
        System.out.print(visited[i][j] + " ");
    }
    System.out.println();
}

 

✔️ 568ms로 시간 개선 : StringBuilder 사용

출력을 할 때마다 System.out.print()를 호출하는 대신, StringBuilder를 사용하여 문자열을 미리 버퍼에 모아 두었다가 한 번에 출력하는 방식으로 변경했다.

StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++){
    for(int j = 0; j < m ; j++){
       sb.append(visited[i][j]).append(" ");
    }
    sb.append("\n");
}

System.out.println(sb);

 

결론은, 알고리즘 문제를 풀 때 입출력까지 포함해서 최적화하는 습관을 들이는 게 중요하다!!

최적화된 입출력 방식을 습관화하자!!!