[PS] 백준 14940 쉬운 최단거리 java 풀이 (자꾸 3%에서 틀리네)

14940번: 쉬운 최단거리 (acmicpc.net)

문제 접근

1. 전형적인 BFS 문제 같다.
2. 시작점부터 시작해서 BFS 시작
3. 그런데 자꾸 3%에서 틀렸다 나오길래 질문게시판을 찾아보았다.

메모리 초과

• 다시 같은 곳을 방문하지 않도록 방문 표시를 해주어야 한다. 안 그러면 Queue에 많은 좌표가 가득차게 된다.

틀렸습니다

• 도달할 수 없는 곳은 -1로 출력을 해야 한다. 이 처리를 안 해주면 3퍼에서 틀렸다고 나온다.

따라서 필자는 방문 표시를 isVisited 배열을 만드는 대신 방문한 곳은 map 값을 -1로 바꾸어주었고, 도달하지 못한 곳은 이 값이 아직 1로 남아있기 때문에 이를 처리해주었다.

코드

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

public class Main {

	static int[] rowDir = {1, -1, 0, 0};
	static int[] colDir = {0, 0, 1, -1};
	static int[][] map;

    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int maxRow = Integer.parseInt(st.nextToken());
		int maxCol = Integer.parseInt(st.nextToken());

		map = new int[maxRow][maxCol];
		int[][] distance = new int[maxRow][maxCol];
		Queue<int[]> dq = new ArrayDeque<>();
		for (int i = 0; i < maxRow; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < maxCol; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 2) {
					dq.offer(new int[]{i, j, 0});
				}
			}
		}

		while(!dq.isEmpty()) {
			int[] current = dq.poll();
			int currentDistance = current[2];
			distance[current[0]][current[1]] = currentDistance;
			for (int i = 0; i < 4; i++) {
				int nextRow = current[0] + rowDir[i];
				int nextCol = current[1] + colDir[i];
				if (0 <= nextRow && nextRow < maxRow && 0 <= nextCol && nextCol < maxCol) {
					if (map[nextRow][nextCol] == 1 && distance[nextRow][nextCol] == 0) {
						map[nextRow][nextCol] = -1; // 방문 표시
						dq.offer(new int[]{nextRow, nextCol, currentDistance + 1});
					}
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < maxRow; i++) {
			for (int j = 0; j < maxCol; j++) {
				if (map[i][j] == 1) { // 도달할 수 없을 때
					sb.append(-1).append(" ");
				} else {

					sb.append(distance[i][j]).append(" ");
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);

	}

}