[백준] S1 14940번 쉬운 최단거리 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

14940번: 쉬운 최단거리

[문제] 

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

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

[입력]

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

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

[출력]

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

 

---

[풀이]

1. BFS를 탐색하기 위한 클래스를 만들어준다.

2. 값들을 입력받아 주고 입력받은 값이 2인 경우 해당 좌표를 설정해준다.

3. BFS 탐색을 하면서 2. 에서 구해둔 좌표를 기준으로 BFS 탐색을 진행한다.

4. 이동 가능한 곳이라면 이전 좌표의 값 + 1을 해준다.

5. 배열의 값이 0이 아니라면 해당 좌표의 값 -2를 해주고 0이라면 0을 넣어준다.

6. 결과를 출력한다.

[접근]

1. BFS로 도착지점부터 기준을 잡고 각 칸의 거리를 측정하면 되겠다고 생각하였다.

[코드]

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

public class Main {
	static int n, m;
	static int map[][];
	static int sx, sy;
	
	static int[] dr = {0, 0, -1, 1};
	static int[] dc = {-1, 1, 0, 0};
	
	static class point {
		int x;
		int y;
		
		public point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new int[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) {
					sx = i;
					sy = j;
				}
			}
		}
		
		bfs();
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] > 0) // 갈 수 있는 곳
					sb.append(map[i][j] - 2 + " "); // 2를 빼주는 이유는 시작을 2로 시작하였기 때문
				else // 못가는 곳
					sb.append(0 + " ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
	
	static void bfs() {
		Queue<point> q = new LinkedList<>();
		// 도착지점을 시작으로 잡음
		q.offer(new point(sx, sy));
		map[sx][sy] = 2; 
		
		while (!q.isEmpty()) {
			point p = q.poll();

			for (int i = 0; i < 4; i++) {
				int nx = p.x + dr[i];
				int ny = p.y + dc[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[p.x][p.y] + 1;
					q.offer(new point(nx, ny));
				}
			}
		}
 	}
}