[백준/Java] 14940 - 쉬운 최단거리

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

문제

---

풀이

최단거리를 구해야하기 때문에 BFS로 해결하였다

주의할 점은 주어진 배열의 값이 0이면 탐색하지 않는다

 

주어진 배열을 탐색하면서 새로운 배열에 값을 넣는데

이전 값(그 좌표까지의 거리) + 1 넣으면서 갱신한다

 

중요한 것은 갈 수 있는 땅인데 도달할 수 없는 부분은 -1로 출력해야한다

방문 배열을 두고 방문 여부를 파악해서 방문하지 않았고 배열 값이 1이면 도달할 수 없는 부분이다

처음에 이 부분을 누락해서 틀렸었다

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int[][] arr;	// 입력 배열
	static int[][] result;	// 결과 배열

	static int[] dx = {-1, 1, 0, 0}; // 상하
	static int[] dy = {0, 0, -1, 1}; // 좌우

	static boolean[][] visited; // 방문 배열

	static int N, M;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N][M];
		visited = new boolean[N][M];
		result = new int[N][M];

		int x = 0;
		int y = 0;
		// 배열을 입력받을 때 2의 위치를 저장한다
		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;
				}
			}
		}

		// 2 위치에서 bfs 탐색 시작
		bfs(x, y);

		// 배열 출력
		for (int i = 0; i < result.length; i++) {
			for (int j = 0; j < result[0].length; j++) {
				// 방문하지 않았고 입력 배열값이 1이라면 
				// (갈 수 있는 땅인 부분 중 도달할 수 없는 위치)
				if (!visited[i][j] && arr[i][j] == 1) {
					// -1 출력
					sb.append(-1).append(" ");
				} else {
					// 목표 지점까지의 거리 출력
					sb.append(result[i][j]).append(" ");
				}
			}
			sb.append("\n");
		}

		System.out.println(sb);

		br.close();
	}

	static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		// 큐에 시작 좌표를 추가
		queue.add(new int[]{x, y});

		// 큐가 빌 때 동안
		while (!queue.isEmpty()) {
			// 큐에서 하나를 꺼냄
			int[] current = queue.poll();

			for (int i = 0; i < 4; i++) {
				// 상하좌우 탐색
				int nx = current[0] + dx[i];
				int ny = current[1] + dy[i];
				// nx, ny가 배열 범위 안이고
				if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
					// 방문하지 않았고 배열값이 1이라면
					if (!visited[nx][ny] && arr[nx][ny] == 1) {
						visited[nx][ny] = true; // 방문 처리
						queue.add(new int[]{nx, ny}); // 큐에 해당 좌표 추가
						// 결과 배열에 이전 값의 +1 한 값 대입
						result[nx][ny] = result[current[0]][current[1]] + 1;
					}
				}
			}
		}
	}
}

결과