BAEKJOON / 백준 - JAVA 14940번 쉬운 최단거리

2024.05.10기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 지도에서 목표 지점까지의 거리를 구하는 문제입니다.

 

문제 접근은 BFS 알고리즘을 이용하여 시작점부터 목표 지점까지의 모든 지점에 대한 거리를 계산을 해보았습니다.

 

boolean[][] visit 변수로 이미 한 번 거리를 계산한 곳은

true로 지정해 다시 거리를 잴 수 없도록 체크하는 변수를 생성합니다.

 

find()라는 함수를 생성해 BFS를 계산을 했습니다.

 

큐에 처음 시작하는 시작점을 넣어줍니다.

 

우선 처음 시작점을 nowx, nowy로 받아 초기화 시켜줬습니다.

그러고 처음 시작점의 길이는 0이므로 0으로 설정해주며 한 번 거리가 측정된 곳은 true로 설정해줍니다.

 

그 다음 큐에 size가 0이 될떄 까지 반복문을 돌려줍니다.

for (int i = 0; i < 4; i++) {
                int nextx = c.x + dx[i];
                int nexty = c.y + dy[i];

이 부분에서 dx와 dy를 nowx, nowy 기준으로 한 칸 위, 아래, 양 옆을 계산을 해주도록 합니다.

if (check(nexty, nextx) && !visit[nexty][nextx]) {
                    visit[nexty][nextx] = true;
                    map[nexty][nextx] = map[c.y][c.x] + 1; // 거리 계산
                    q.add(new Coordinate(nextx, nexty));
                }

그 다음 거리를 설정해야될 x, y좌표에

1. 좌표가 범위 안에있는지
2. 좌표에 거리가 아직 설정이 안되어 있는지

를 체크 해주어야 됩니다.

여기서 체크를 안해주게 되면 이미 계산된 거리가 중복으로 계산되는 문제가 발생하기 때문에 주의해야 합니다.

 

그리고 2조건이 만족한다면,

1. 만족의 했기 때문에 거리를 계산을 합니다.
2. 계산을 하기 때문에 true로 거리가 설정되었다는걸 체크해줍니다.
3. 지금 참조하고 있는 x, y좌표의 부모 x, y좌표의 거리보다 +1 로 설정하여 거리를 설정합니다.
4. 그리고 참조된 x와 y좌표를 큐에 넣어 다시 반복문을 반복하게 됩니다.

 

 

코드

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

public class Main {
	
    	// 좌표 클래스 정의
	public static class Coordinate {
		int x, y;
		
		public Coordinate(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int h, w;
	static int[][] map;
	static int[] dx = {0, 1, 0, -1}; // 상하좌우 이동을 위한 배열
	static int[] dy = {-1, 0, 1, 0};
	static boolean[][] visit;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		h = Integer.parseInt(st.nextToken());
		w = Integer.parseInt(st.nextToken());
		map = new int[h][w];
		visit = new boolean[h][w];
		
		int x = 0;
		int y = 0;
		
		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < w; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				if (map[i][j] == 0) { // 시작점은 방문한 것으로 처리
					visit[i][j] = true;
				}
				
				if (map[i][j] == 2) { // 시작점의 좌표 저장
					x = j; 
					y = i;
				}
			}
		}
		
        	// 목표 지점까지의 거리 구하기
		find(x, y);
		
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (!visit[i][j]) {
					map[i][j] = -1; // 도달할 수 없는 지점은 -1로 표시
				}
				
				sb.append(map[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
    	// BFS를 이용하여 목표 지점까지의 거리 구하기
	private static void find(int x, int y) {
		Queue<Coordinate> q = new LinkedList<>();
		q.add(new Coordinate(x, y));
		
        	// 시작점 초기화
		int nowx = x;
		int nowy = y;
		map[nowy][nowx] = 0;
		visit[nowy][nowx] = true;
		
        	// BFS 수행
		while (!q.isEmpty()) {
			Coordinate c = q.remove();
			
           	 	// 상하좌우 이동 확인
			for (int i = 0; i < 4; i++) {
				int nextx = c.x + dx[i];
				int nexty = c.y + dy[i];
				
                		// 범위 확인 및 방문 여부 확인
				if (check(nexty, nextx) && !visit[nexty][nextx]) {
					visit[nexty][nextx] = true;
					map[nexty][nextx] = map[c.y][c.x] + 1; // 거리 계산
					q.add(new Coordinate(nextx, nexty));
				}
			}
		}
	}
	
    	// 좌표가 범위 내에 있는지 확인하는 메서드
	private static boolean check(int y, int x) {
		return 0 <= x && 0 <= y && y < h && x < w;
	}
}