본문 바로가기
PS/BOJ

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

by Nahwasa 2023. 2. 14.

 문제 : 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);
    }
}

댓글