[BOJ_14940] 쉬운 최단거리

설명

---

최단 거리로 가지는 곳을 찍으면 된다. 조건 중 벽에 막혀서 못 가는 부분만 -1으로 출력 하라는 부분을 신경쓴다면 일반적인 미로 탐색 로직 처럼 짜면 된다.

 

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static boolean [][] visited;
    static int map[][] ;
    static List<Integer>[] graph;
    static int dx[] = {-1,0,1,0};
    static int dy[] = {0,-1,0,1};
    static int time[][];

    static int N,M;
    static class Data{
        int x;
        int y;
        public Data(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        N = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());

        map = new int[N][M];
        time = new int[N][M];
        visited = new boolean[N][M];

        int startX = 0;
        int startY = 0;
        for (int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine()," ");
            for (int j = 0; j < M; j++){
                map[i][j] = Integer.parseInt(tk.nextToken());
                if(map[i][j] == 2){
                    startX = i;
                    startY = j;
                }else if (map[i][j] == 1){
               time[i][j] = -1;
               }
            }
        }
        bfs(startX,startY);
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++) {
                System.out.print(time[i][j] + " ");
            }
            System.out.println();
        }
    }
    private static void bfs(int X, int Y){
        Queue<Data> q = new LinkedList<Data>();
        q.add(new Data(X,Y));
        visited[X][Y] = true;
        time[X][Y] = 0;
        while (!q.isEmpty()){
            Data now = q.poll();
            for (int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx >= N || ny >= M || nx < 0 || ny < 0 || visited[nx][ny] || map[nx][ny] == 0){
                    continue;
                }
                else{
                    visited[nx][ny] = true;
                    time[nx][ny] = time[now.x][now.y] + 1;
                    q.add(new Data(nx,ny));
                }
            }
        }
    }
}

14940번: 쉬운 최단거리