[S1] 쉬운 최단거리 : 14940 : Java - BFS

1. 💎 문제

14940번: 쉬운 최단거리

 

 

 

2. 🤔 어떻게 풀까

이 문제는 점점 물들이는 문제로 익숙한 BFS문제로 느껴졌다. 그래서 BFS로 풀기로 하였고 출력 결과를 봤을 때 시작 점을 기준으로 거리가 늘어나는 것을 보아 시작점부터 탐색을 진행하며, depth을 관리하면서 풀면 되겠구나 생각했다.

 

 

3. 💡로직

1. 지도를 입력 및 시작점 받기

이중 for문으로 지도를 입력받는 형태에서 stream을 이용한 형태로 바꿨는데 시간이 훨씬 단축되는 것 같다.

// Input
map = new int[row][col];

int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
        
        for (int i = 0; i < row; i++) {
            map[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            for(int j=0; j<col; j++){
                if(map[i][j] == 2){
                    start =  new Point(i, j);
                    break;
                }
            }
        }

 

 

2. 최단 거리 구하기

시작점을 시작으로 큐에 넣어가며 상하좌우 요소를 확인한다. 이때 요소가 갈 수있는 위치(1)이면 큐에 위치 정보를 삽입하고, 최단거리를 저장하는 `distances` 배열에 현재 distance 값 +1 값을 넣어준다.

 // start 부터
        distances[start.x][start.y] = 0;
        isVisited[start.x][start.y] = true;
        que.add(start);

        while (!que.isEmpty()) {
            Point curData = que.poll();
            for (int i = 0; i < 4; i++) {
                int r = curData.x + dx[i];
                int c = curData.y + dy[i];

                if(r>=0 && r<row && c>=0 && c<col){
                    if (map[r][c] ==1 && !isVisited[r][c]) {
                        que.add(new Point(r, c));
                        isVisited[r][c] = true;
                        distances[r][c] = distances[curData.x][curData.y] +1;
                    }
                }

            }
        }

 

 

3. 최단거리 출력

과정 2에서 추가한 `distance`값을 출력한다. 이때 '갈 수 있는 땅(1)인 부분 중 도달할 수 없는 땅'은 따로 처리하여 -1을 출력하도록 한다.

 // output
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 갈 수 있는 땅인 부분 중 도달할 수 없음
                if(map[i][j]==1 && distances[i][j] == 0){
                    bw.write(-1 + " ");
                    continue;
                }
                bw.write(distances[i][j] + " ");
            }
            bw.write("\n");
        }
        bw.flush();

        bw.close();
        br.close();

 

 

 

3. 📄 전체 코드

import java.awt.*;
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ_쉬운_최단거리_14940 {

    static BufferedReader br;
    static BufferedWriter bw;
    static Queue<Point> que;
    static int [][] map;
    static boolean [][] isVisited;
    static int [][] distances;
    static Point start;

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

    public static void main(String[] args) throws Exception {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());

        distances = new int[row][col];
        isVisited = new boolean[row][col];
        map = new int[row][col];
        que = new LinkedList<>();

        // Input
        for (int i = 0; i < row; i++) {
            map[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            for(int j=0; j<col; j++){
                if(map[i][j] == 2){
                    start =  new Point(i, j);
                    break;
                }
            }
        }

        // start 부터
        distances[start.x][start.y] = 0;
        isVisited[start.x][start.y] = true;
        que.add(start);

        while (!que.isEmpty()) {
            Point curData = que.poll();
            for (int i = 0; i < 4; i++) {
                int r = curData.x + dx[i];
                int c = curData.y + dy[i];

                if(r>=0 && r<row && c>=0 && c<col){
                    if (map[r][c] ==1 && !isVisited[r][c]) {
                        que.add(new Point(r, c));
                        isVisited[r][c] = true;
                        distances[r][c] = distances[curData.x][curData.y] +1;
                    }
                }

            }
        }

        // output
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 갈 수 있는 땅인 부분 중 도달할 수 없음
                if(map[i][j]==1 && distances[i][j] == 0){
                    bw.write(-1 + " ");
                    continue;
                }
                bw.write(distances[i][j] + " ");
            }
            bw.write("\n");
        }
        bw.flush();

        bw.close();
        br.close();
    }
}