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

문제 링크

성능 요약

메모리: 75700 KB, 시간: 2340 ms

분류

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

제출 일자

2024년 2월 26일 14:26:01

문제 설명

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

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

### 입력

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

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

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -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 arr[][], result[][], n, m;
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	static boolean visited[][];
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());

		// 지도의 크기
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());

		arr=new int[n][m]; // 지도
		result=new int[n][m]; // 거리
		visited=new boolean[n][m]; // 방문 여부
		int x=0,y=0;
		for(int i=0; i<n; i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
				if(arr[i][j]==2) {  // 목표 지점
					x=i;
					y=j;
				}else if(arr[i][j]==0) visited[i][j]=true; // 갈 수 없는 땅
			}
		}
		bfs(x,y);

		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(!visited[i][j]) { // 도달할 수 없는 위치
					result[i][j]=-1;
				}	
				System.out.print(result[i][j]+" ");	
			}
			System.out.println();
		}
	}
	private static void bfs(int x, int y) {
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {x,y});
		visited[x][y]=true;

		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			for(int i=0; i<4; i++) {
				int a=temp[0]+dx[i];
				int b=temp[1]+dy[i];
				if(a>=0 && a< n && b>=0 && b<m) {
					if(!visited[a][b] && arr[a][b]==1) {
						visited[a][b]=true;
						result[a][b]=result[temp[0]][temp[1]]+1;
						queue.add(new int[] {a,b});
					}
				}
			}
		}
	}
}

[문제 풀이 참고]