Baekjoon 14940 쉬운 최단거리 JAVA

14940번: 쉬운 최단거리

문제

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

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

입력

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

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

출력

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

풀이

각 지점에서 목표지점으로 가는 것이 아니라, 목표지점에 각 지점으로 탐색을 하는 방법을 사용한다.

1. 지도의 내용을 입력받으면서 갈 수 없는 땅과 시작할 위치 (목표지점)을 찾음

2. 나머지 위치들을 -1로 초기화 ( 원래 갈 수 있지만 도달할 수 없는 위치를 위함 )

3. BFS를 돌면서 방문체크를 할때 depth만큼 값을 지정함

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
		int [][] map = new int[n][m], ans=new int[n][m];
		int sx=0, sy=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) {	// 입력이 2이면 도착위치지만 BFS에서는 시작위치로 만드는 것이 편함
					sx=i;
					sy=j;
				}
				else if(map[i][j]==0)	// 원래 벽이 있는 위치면 0으로 출력한다
					ans[i][j]=0;
				else			// 아무것도 아니면 원래 갈 수 잇는 위치이기에 기본 출력 값을 -1로 설정
					ans[i][j]=-1;
			}	
		}
		Queue<int []> q = new LinkedList<int[]>();
		int [] dx= {-1,1,0,0}, dy= {0,0,1,-1};
		q.add(new int[] {sx,sy, 0});
		while(q.size()>0) {
			int [] cur = q.poll();
			int x=cur[0], y=cur[1], v=cur[2];
			
			for(int i=0;i<4;i++) {
				if(x+dx[i]<0 || x+dx[i]>=n || y+dy[i]<0 || y+dy[i]>=m)
					continue;
				if(map[x+dx[i]][y+dy[i]]==1 && ans[x+dx[i]][y+dy[i]]==-1) {	// 사방탐색을 하며 갈수 있는 길이면서, 방문하지 않았을 떄만 방문
					q.add(new int[] {x+dx[i], y+dy[i], v+1});
					ans[x+dx[i]][y+dy[i]]=v+1;
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++)
				bw.write(ans[i][j]+" ");
			bw.write("\n");
		}
		bw.close();
	}
}