[백준 14940] 쉬운 최단거리 (JAVA)

백준 14940번 문제 - 쉬운 최단거리

14940번: 쉬운 최단거리

---

문제 분석

 

•  

 

• 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
  
  • 갈수없는 땅 : 0
  • 갈 수 있는 땅 : 1
  • 목표지점: 2
• 각 지점에서 목표지점까지의 거리를 출력한다. 
  • 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

---

해결 포인트

 

• 목표지점까지 거리를 담는 2차원 배열 map의 모든 값을 -1 로 초기화
  
  •  Arrays.fill(newMap[i], -1);
• BFS 사용 
  • 시작할 때, 목표 지점은 0으로 설정 및 queue에 추가
  • 큐에 담겨진 모든 위치를 빼고, 그 근처 값들은 큐에 넣기
  • 큐에 넣을 때 map에 해당 위치를 count 로 설정
  • count는 while이 반복될 때마다 하나씩 증가
• 기존에 입력받은 map 이 0일 경우, 해당 위치는 0 출력 | 0이 아닐 경우 BFS로 구한 위치 값 출력

---

코드

 

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

public class Main {
    public static int n,m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        int [][] map = new int[n][m];
        int finalN = 0;
        int finalM = 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) {
                    finalN = i;
                    finalM = j;
                }
            }
        }

        int [][] newMap = BFS(map, finalN, finalM);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j] == 0)
                    newMap[i][j] = 0;
                bw.write(newMap[i][j] + " ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    public static int [][] BFS(int [][] map, int x, int y) {
        boolean [][] visit = new boolean[n][m];
        int [][] newMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(newMap[i], -1);
        }

        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(x, y));
        visit[x][y] = true;
        newMap[x][y] = 0;

        int [] dx = {0,0,1,-1};
        int [] dy = {1,-1,0,0};

        int count = 1;
        while(!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int q = 0; q < queueSize; q++) {
                Point value = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = value.x + dx[i];
                    int ny = value.y + dy[i];

                    if (isCheckRound(nx, ny) && !visit[nx][ny] && map[nx][ny] == 1) {
                        newMap[nx][ny] = 0;
                        visit[nx][ny] = true;

                        queue.add(new Point(nx, ny));
                        newMap[nx][ny] = count;
                    }
                }
            }
            count++;
        }

        return newMap;
    }

    public static boolean isCheckRound(int x, int y) {
        return x >= 0 && y>= 0 && x < n && y < m;
    }
}