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

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

문제 링크

성능 요약

메모리: 83384 KB, 시간: 592 ms

분류

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

제출 일자

2024년 10월 16일 01:34:05

문제 설명

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

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

입력

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

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

출력

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

제출코드

//https://www.acmicpc.net/problem/14940
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);
        int[][] map = new int[n][m];
        Queue<int[]> q = new LinkedList<>();
        for(int x=0;x<n;x++){
            temp = br.readLine().split(" ");
            for(int y=0;y<m;y++){
                map[x][y] = Integer.parseInt(temp[y]);
                if(map[x][y]==2){q.offer(new int[]{x,y,0});}
            }
        }

        // bfs
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        int[] now;
        int x,y;

        while(!q.isEmpty()){
            now = q.poll();
            map[now[0]][now[1]] = now[2];
            for(int d=0;d<4;d++){
                x=now[0]+dx[d];
                y=now[1]+dy[d];
                if(x>=0 && x<n && y>=0 && y<m && map[x][y] == 1){
                    map[x][y] = now[2]-1;
                    q.add(new int[]{x,y,now[2]-1});
                }
            }

        }

        // answer
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                bw.write(-1*map[i][j]+" ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();

    }
}