[Baekjoon] 14940 - 쉬운 최단거리

📝 문제

 

 

🔑 풀이 과정

· 기본적인 BFS 문제. 각 지점에서 목표지점까지의 거리 = 목표지점에서 각 지점으로의 거리 이므로, 목표지점을 시작점으로 BFS를 수행하면 된다.

 

· 출력 부분을 잘 보면 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력하라 되어있다. 예제 입력에는 이 부분이 없어서 놓칠 수 있으니 주의하자.

 

· 나 같은 경우는 n, m이 최대 1000이라 매우 작기때문에 전체탐색을 해도 시간초과가 나지 않을거라 생각하였고, BFS 완료 후 방문배열과 입력배열을 전체탐색해서 방문배열이 false고, 입력배열이 갈 수 있는 땅(1)인 곳은 -1을 넣어줬다.

 

· 아니면 출력을 할 때 위 같은 조건이면 -1, 아니면 결과배열의 값을 출력하기. 이런식으로 진행해도 된다,

 

 

🔓 답안

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

    static int n;
    static int m;

    static int[][] map;
    static int[][] result;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        //입력
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); //가로 길이
        m = Integer.parseInt(st.nextToken()); //세로 길이

        map = new int[n][m]; //지도 생성
        result = new int[n][m]; //결과를 넣을 배열 생성
        visited = new boolean[n][m]; //방문 배열

        //지도 입력받기
        int startRow = 0;
        int startCol = 0;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++){
                map[i][j] = Integer.parseInt(st.nextToken());

                //목표 지점의 위치 저장
                if(map[i][j] == 2){
                    startRow = i;
                    startCol = j;
                }
            }
        }

        //목표지점부터 BFS 수행
        BFS(startRow, startCol);

        //BFS 후 방문이 안되어있는 갈 수 있는 땅(1)은 -1값을 가져야 함
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m ; j++){
                if((!visited[i][j]) && (map[i][j] == 1)){
                    result[i][j] = -1;
                }
            }
        }

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

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    //BFS 메서드
    static void BFS(int row, int col){
        Queue<int[]> queue = new LinkedList<>();
        visited[row][col] = true;
        queue.add(new int[] {row, col});

        while(!queue.isEmpty()){
            int[] now = queue.remove();
            int nowRow = now[0];
            int nowCol = now[1];

            for(int i = 0; i < 4; i++){
                int newRow = nowRow + dx[i];
                int newCol = nowCol + dy[i];

                if((newRow >= 0) && (newRow < n) && (newCol >= 0) && (newCol < m)){
                    if((!visited[newRow][newCol]) && (map[newRow][newCol] == 1)){
                        result[newRow][newCol] = result[nowRow][nowCol] + 1;
                        visited[newRow][newCol] = true;
                        queue.add(new int[] {newRow, newCol});
                    }
                }
            }
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색