[최단경로] 백준 14940 쉬운 최단거리 자바 (Java)

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

14940번: 쉬운 최단거리

 

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

 

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

코드

시간초과

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class No14940 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] map = new int[n][m];
        int[][] result = new int[n][m];
        int [] dx= {-1,1,0,0}, dy= {0,0,1,-1};
        int sx = 0, sy = 0;
        for(int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                map[i][j] = sc.nextInt();
                if(map[i][j] == 2){ //도착 위치를 bfs가 시작 하는 위치로 설정
                    sx = i;
                    sy = j;
                } else if (map[i][j] == 0) {
                    result[i][j] = 0;
                } else {
                    result[i][j] = -1;
                }
            }
        }

         //bfs
        Queue<int []> q = new LinkedList<int []>();
        q.add(new int[] {sx, sy, 0});

        while(!q.isEmpty()) {
            int [] cur = q.poll();
            for(int i = 0; i < 4; i++) { //상하좌우 4가지
                int nx = cur[0] + dx[i], ny = cur[1] + dy[i], nv = cur[2]; //nv는 방문 여부
                if(nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;
                if(map[nx][ny] == 1 && result[nx][ny] == -1) {
                    q.add(new int[] {nx, ny, nv + 1});
                    result[nx][ny] = nv + 1;
                }
            }
        }

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

scanner에서 bufferReader로 수정하여 시간초과 안나게 함

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

public class No14940 {
    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[][] map = new int[n][m];
        int[][] result = new int[n][m];
        int [] dx= {-1,1,0,0}, dy= {0,0,1,-1};
        int sx = 0, sy = 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){ //도착 위치를 bfs가 시작 하는 위치로 설정
                    sx = i;
                    sy = j;
                } else if (map[i][j] == 0) {
                    result[i][j] = 0;
                } else {
                    result[i][j] = -1;
                }
            }
        }

        //bfs
        Queue<int []> q = new LinkedList<int []>();
        q.add(new int[] {sx, sy, 0});

        while(!q.isEmpty()) {
            int [] cur = q.poll();
            for(int i = 0; i < 4; i++) { //상하좌우 4가지
                int nx = cur[0] + dx[i], ny = cur[1] + dy[i], nv = cur[2]; //nv가 1보다 크면 방문한 곳이고, depth를 나타낸다
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) //map 안에 있는지 검사
                    continue;
                if(map[nx][ny] == 1 && result[nx][ny] == -1) { //이동 가능 한 곳인지 && 처음 방문 하는 곳인지 검사
                    q.add(new int[] {nx, ny, nv + 1});
                    result[nx][ny] = nv + 1;
                }
            }
        }

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

풀이

bfs를 이용하여 푸는 문제

노드의 depth가 해당 노드의 목표지점까지의 거리를 나타 내는 것이다.

bfs 탐색을 하면서 얻은 depth를 2차원 배열에 넣고 2차원 배열을 출력하면 정답이다.

 

 

주의 사항

scanner를 사용하면 시간 초과가 나는 문제

 

최단경로 푸는 방법

문제유형	푸는 방법
가중치 개념이 없는 최단 경로 문제	BFS
가중치 개념이 있는 한 노드 기준 최단 경로 문제	다익스트라
가중치 개념이 있는 여러 노드 기준 최단 경로 문제	플로이드 와샬