[백준_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.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 StringBuilder sb=new StringBuilder();
	static int[][] map;
	static int n,m,endx,endy;
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		map=new int[n][m];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				map[i][j]=sc.nextInt();
				
				if(map[i][j]==2) {
					endx=i;
					endy=j;
				}
			}	
		}
		
		bfs();
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				/*
				 * 도착 지점의 배열 2 값으로 시작하면서 배열의 값을 늘려줬기 때문에 
				 * 갈 수 없는 땅의 위치인 0을 제외한 배열 값은 초기 값인 2를 빼준 값을 출력해야 한다.   
				 */
				if(map[i][j]>0)
					sb.append(map[i][j]-2+" ");
				// 갈 수 없는 땅인 곳은 0으로 출력
				else
					sb.append(0+" ");
			}
			sb.append('\n');
		}
		
		System.out.println(sb);
	}
	
	static void bfs() {
		Queue<Point_14940> q=new LinkedList<>();
		q.offer(new Point_14940(endx,endy)); // 시작지점 큐에 삽입
		map[endx][endy]=2; // 시작지점 
		
		while(!q.isEmpty()) {
			Point_14940 point=q.poll();
			int x=point.x;
			int y=point.y;

			// 상,하,좌,우 탐색
			for(int i=0;i<4;i++) {
				int nx=x+dx[i];
				int ny=y+dy[i];
				
				// 범위를 벗어나거나 갈 수 없는 땅인 경우 넘어간다.
				if(nx<0||ny<0||nx>=n||ny>=m||map[nx][ny]==0)
					continue;
				
				// 갈 수 있는 땅이라면 이전 배열의 값에 +1한 값으로 배열 값 갱신
				if(map[nx][ny]==1) {
					map[nx][ny]=map[x][y]+1;
					q.offer(new Point_14940(nx,ny));
				}
			}
		}
 	}
}

 

[고찰]

 이번 문제는 도착 지점으로부터 각 좌표가 얼만큼 떨어져있는지 BFS 알고리즘을 사용하여 구하는 문제였다. 도착 지점을 시작으로 상, 하, 좌, 우 탐색하여 갈 수 있는 땅이라면 이전 배열의 값에 +1 해준 값으로 갱신하고 큐에 넣어준다. 처음에 시작 지점은 0으로 출력해야 하기 때문에 0으로 초기화 하고 BFS를 시작했는데 예제 문제의 배열 (1,0)과 (0,1)의 값이 1이 아닌 3으로 출력되는 오류가 있었다. 출력을 통해 이유를 알아보고자 했는데 처음 계산되는 값은 1이지만 이후 과정에서 3으로 바뀌는 것을 확인했다. 정확한 이유는 알 수 없어 도착 지점의 값을 0으로 초기화 하지 않고 2로 시작하고 이후 배열 값이 0 이상인 곳만 -2를 해주는 방식으로 해결했다.