[JAVA] 백준 14940번: 쉬운 최단거리

 

---

문제

• 2차원의 형태로 1은 지나갈 수 있는 길, 0은 벽, 2가 출발지로 주어질 때, 출발지에서 모든 다른 지점까지의 최단 거리를 2차원 형태로 출력하는 문제.

 

아이디어

• 최단거리를 구하는 문제로, BFS를 사용해 풀이한다.
• 입력을 받으며 2의 위치를 먼저 큐에 넣어놓고 해당 경로를 0으로 초기화 한 후, BFS를 돌린다.
• BFS를 돌리며 최단거리를 갱신하고 과정이 모두 끝난 후, 각 요소를 탐색해 길인데 도달하지 못한 요소를 -1로 변경한 후 출력해준다.

 

풀이

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

public class Main {
    static int n, m;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Deque<int[]> queue = new ArrayDeque<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        visited = new boolean[n][m];
        
        // 그래프 입력
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                // 출발 좌표 큐에 저장
                if(graph[i][j] == 2) {
                    queue.addLast(new int[]{i, j});
                    // BFS 도중 경로 갱신에 사용하기 위해 출발지를 0으로 초기화
                    graph[i][j] = 0;
                    visited[i][j] = true;
                }
            }
        }
        bfs();
        
        // 모든 요소 탐색 중, 길인데 도달할 수 없으면 -1로 변경
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(graph[i][j] == 1 && !visited[i][j]) {
                    graph[i][j] = -1;
                }
                sb.append(graph[i][j]).append(' ');
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }
    
    static void bfs() {
        while(!queue.isEmpty()) {
            int[] tmp = queue.removeFirst();
            int x = tmp[0];
            int y = tmp[1];
            for(int i=0; i<4; i++) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(nx<0 || ny<0 || nx>=n || ny>=m) {
                    continue;
                }
                // 방문하지 않았고, 길이면 최단경로 갱신
                if(!visited[nx][ny] && graph[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    graph[nx][ny] = graph[x][y]+1;
                    queue.addLast(new int[]{nx, ny});
                }
            }
        }
    }
}

 

채점 결과

14940번 채점 결과

 

문제 링크

• 14940번: 쉬운 최단거리 (acmicpc.net)