[자바] 백준 14940 - 쉬운 최단거리 (java)

 문제 : boj14940

---

 

필요 알고리즘 개념

• 그래프, 너비 우선 탐색 (BFS)
  
  • 그래프에 대한 약간의 규칙을 이해할 수 있어야 한다. 그것만 이해하면 그냥 BFS 한방에 해결 가능하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  모든 지점에서 목표지점까지의 최단 거리는 사실, 목표지점에서 모든 지점으로의 최단 거리와 같다. 사실 간선이 양방향이니 당연한 부분이다. 이것만 알면 그냥 목표지점부터 BFS를 한방 돌려서 모든 지점에 대한 거리만 계산하면 끝난다!

 

  참고로 이 문제가 단방향 그래프여도 비슷하게 할 수 있는데, 알아두면 여러모로 써먹기 좋다. 모든 간선의 방향을 역방향으로 돌린 후 목표지점에서 출발해 BFS 돌리면 그게 모든 지점에서 목표지점까지의 거리와 동일해진다. 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int BLOCK = -2;
    private static final int[] DR = {-1, 0, 0, 1};
    private static final int[] DC = {0, 1, -1, 0};

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        Queue<int[]> q = new ArrayDeque<>();
        int[][] d = new int[r][c];
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                char cur = st.nextToken().charAt(0);
                d[i][j] = cur != '0' ? -1 : BLOCK;
                if (cur == '2') {
                    q.add(new int[]{i, j});
                    d[i][j] = 0;
                }
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nr = cur[0] + DR[i];
                int nc = cur[1] + DC[i];
                if (nr < 0 || nr >= r || nc < 0 || nc >= c) continue;
                if (d[nr][nc] == BLOCK || d[nr][nc] >= 0) continue;
                d[nr][nc] = d[cur[0]][cur[1]] + 1;
                q.add(new int[]{nr, nc});
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (d[i][j] == BLOCK) sb.append(0);
                else sb.append(d[i][j]);
                sb.append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}