[백준] 14940번 : 쉬운 최단거리 Silver1(실버1) - JAVA[자바]

[Silver I] 쉬운 최단거리 - 14940

문제 링크

성능 요약

메모리: 81452 KB, 시간: 664 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2023년 12월 12일 10:15:01

문제 설명

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

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

입력

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

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

출력

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

 

풀이 방법

1. 값을 읽어들일 때 시작점 위치를 기억해준다.

2. 1이라면 -1로 기록(방문하지 못한 곳은 -1로 처리해줘야하기 때문에)

3. 0이라면 그대로 기록

4. bfs로 방문한다.(bfs는 순차적으로 방문하기 때문에 처음 방문값이 최소값임)

5. 범위 밖이거나 Or 이미 방문했거나(-1이아닐 때) Or 벽일 때는 Continue;

6. 현재 위치에서 +1 하고 값 삽입하기

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

public class Main {
    static int[][] answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        answer = new int[a][b];

        int[] start = new int[2];
        for (int i = 0; i < a; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < b; j++) {
                int tmp = Integer.parseInt(st.nextToken());
                // 1아러묜 방문하지 못한 위치는 -1로 처리해야해서 미리 삽입
                if (tmp == 1) {
                    answer[i][j] = -1;
                }
                // 시작점일 때 위치 기억
                else if (tmp == 2) {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }
        bfs(start);
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                sb.append(answer[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static void bfs(int[] start) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        int[] dirX = {0, 0, -1, 1};
        int[] dirY = {-1, 1, 0, 0};

        while (!queue.isEmpty()) {
            // 현재 위치 기억
            int[] cur = queue.poll();

            // 상,하,좌,우순으로 확인하기
            for (int i = 0; i < 4; i++) {
                int nX = cur[0] + dirX[i];
                int nY = cur[1] + dirY[i];
                // nX, nY가 범위밖일 때는 Continue;
                if (nX < 0 || nX >= answer.length || nY < 0 || nY >= answer[nX].length) {
                    continue;
                }
                // -1이 아니라면(벽이거나 방문했다면) continue;
                if (answer[nX][nY] != -1) {
                    continue;
                }
                // 현재 위치 + 1로 최소값 삽입 후 큐에 넣어준다.
                answer[nX][nY] = answer[cur[0]][cur[1]] + 1;
                queue.offer(new int[] {nX, nY});
            }
        }
    }
}