[백준_14940번] 쉬운 최단거리

https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

 

[문제]

 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

 

[입력 조건]

• 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
• 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

 

[코드]

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

class Point_14940 {
	int x,y;
	
	public Point_14940(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_14940 {
	static int[][] map,distance;
	static boolean[][] visited;
	static int n,m,start_x,start_y;
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		StringBuilder sb=new StringBuilder();
		
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		map=new int[n][m];
		distance=new int[n][m];
		visited=new boolean[n][m];
		
		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) {
					start_x=i;
					start_y=j;
				}
			}
		}
		
		BFS(start_x, start_y);
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(!visited[i][j]&&map[i][j]==1)
					sb.append(-1+" ");
				else
					sb.append(distance[i][j]+" ");
			}
			sb.append('\n');
		}
		System.out.println(sb);
	}
	
	static void BFS(int x, int y) {
		Queue<Point_14940> q=new LinkedList<>();
		visited[x][y]=true;
		q.add(new Point_14940(x,y));
		
		while(!q.isEmpty()) {
			Point_14940 now=q.poll();
			
			for(int i=0;i<4;i++) {
				int nx=now.x+dx[i];
				int ny=now.y+dy[i];
				
				if(nx>=0&&ny>=0&&nx<n&&ny<m) {
					if(map[nx][ny]!=0&&!visited[nx][ny]) {
						distance[nx][ny]=distance[now.x][now.y]+1;
						visited[nx][ny]=true;
						q.add(new Point_14940(nx,ny));
					}
				}
			}
		}
	}
}

 

[고찰]

 이번 문제는 DFS&BFS 문제를 많이 풀어봤다면 쉽게 해결할 수 있는 최단거리 문제였다. 배열의 값이 2인 시작지점으로 부터 모든 칸까지의 거리를 계산하면 되는 문제로 출력 부분만 신경써주면 된다.

 도달할 수 없는 곳은 -1을 출력해주는 부분과 Scanner를 사용하여 시간초과가 난 것을 고치니 정답 처리를 받을 수 있었다.