[백준/자바] 14940번: 쉬운 최단거리

문제

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

풀이

• 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하라
• 움직일 수 있는 방향은 가로, 세로

기초적인 BFS 문제입니다.

저는 처음에 결과를 나타낼 배열을 하나 더 만들어 제출했지만, 메모리 초과가 발생해 최적화를 진행했습니다.

		map = 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) { // 현재 좌표가 목적지일 경우
					sr = i; sc = j; // 출발 좌표 설정
				} else if (map[i][j] == 0) visited[i][j] = true; // 갈 수 없는 땅인 경우 방문처리
			}
		}

• 갈 수 없는 땅인 경우 방문 처리해주어, 이후 탐색을 진행할 때 진입하지 못하게 하였습니다.
• 또한, 갈 수 있는 땅인데 탐색을 못했다면 -1을 출력해야 하므로 갈 수 없는 땅은 미리 방문 처리를 해놨습니다.

	private static void bfs() {
		visited[sr][sc] = true; // 시작 지점 방문 처리
		
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {sr, sc}); // 시작 지점 큐에 삽입
		map[sr][sc] = 0; // 목적지까지의 거리 (현재 좌표이므로 0)
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1];
			
			for (int i = 0; i < 4; i++) { // 4방 탐색
				int nr = r + dr[i];
				int nc = c + dc[i];
				
                // 범위 밖이거나, 이미 방문한 좌표라면 pass
				if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc]) continue;
				
				map[nr][nc] = map[r][c] + 1; // 다음 좌표는 현재 좌표의 거리 + 1
				visited[nr][nc] = true; // 방문 처리
				queue.add(new int[] { nr, nc }); // 다음 좌표 큐에 삽입
			}
		}
	}

• 답을 출력할 새로운 배열이 아닌 기존 배열을 이용해 탐색 결과를 저장했습니다.

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!visited[i][j]) sb.append(-1).append(" "); // 방문하지 않은 좌표라면 -1
				else sb.append(map[i][j]).append(" "); 아니라면 값 출력
			}
			sb.append('\n');
		}

• StringBuilder에 저장하여 한 번에 출력하였습니다.

코드

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

public class Main_14940 {
	static StringBuilder sb = new StringBuilder();
	static int n, m, sr, sc;
	static int[][] map;
	static boolean[][] visited;
	
	static final int[] dr = { -1, 1, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1 };
	
	private static void bfs() {
		visited[sr][sc] = true;
		
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {sr, sc});
		map[sr][sc] = 0;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1];
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc]) continue;
				
				map[nr][nc] = map[r][c] + 1;
				visited[nr][nc] = true;
				queue.add(new int[] { nr, nc });
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		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];
		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) {
					sr = i; sc = j;
				} else if (map[i][j] == 0) visited[i][j] = true;
			}
		}
		
		bfs();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!visited[i][j]) sb.append(-1).append(" ");
				else sb.append(map[i][j]).append(" ");
			}
			sb.append('\n');
		}
		
		System.out.println(sb.toString());
	}

}