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

0. 문제 링크

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

14940번: 쉬운 최단거리

 

1. 문제 설명

1) 모든 지점에 대해서 목표지점까지의 거리 구하기

2) 0 : 갈 수 없는 땅, 1 : 갈 수 있는 땅, 2 : 목표 지점

3) 원래 갈 수 있는 땅 중 도달할 수 없으면 -1 출력

 

2. 입출력

// input
15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

// output
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

 

3. 코드

import java.awt.Point;
import java.io.*;
import java.util.*;

class Pos{
	int r, c, cnt;
	
	public Pos(int r, int c, int cnt) {
		this.r = r;
		this.c = c;
		this.cnt = cnt;
	}
}

public class b14940 {
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] map = new int[N][M];
		int[][] v = new int[N][M];
		
		Pos start = new Pos(0, 0, 0);
		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) { // 목표 지점 설정
					start.r = i;
					start.c = j;
					start.cnt = 0;
				} 
				else if(map[i][j] == 1) { // 갈 수 있는 땅
					v[i][j] = -1; // 도달할 수 없으면 -1
				}
			}
		}
		
		Queue<Pos> q = new LinkedList<Pos>();
		q.offer(start); // 시작 지점 추가
		
		while(!q.isEmpty()) { // 큐가 빌 때까지
			Pos p = q.poll(); // 큐에서 하나 꺼내기
			for (int i = 0; i < 4; i++) { // 사방탐색
				int nr = p.r + dr[i];
				int nc = p.c + dc[i];
				// 범위 내에 있고, 갈 수 있는 땅이며, 아직 안 갔으면
				if(nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] == 1 && v[nr][nc] == -1) {
					v[nr][nc] = p.cnt + 1;
					q.offer(new Pos(nr, nc, p.cnt + 1));
				}
			}
		}
		
		// 출력
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				sb.append(v[i][j]).append(" "); 
			}
			sb.append("\n");
		}		
		System.out.println(sb);
	}

}

 

실행 결과

 

4. 회고

1) 모든 지점에서 목표 지점까지의 거리를 구하는 문제이지만, 반대로 생각해서 목표 지점에서 모든 지점까지의 거리를 구하는 방법으로 생각

2) 모든 경우를 가지치기 하듯 퍼져 나가는 방식이므로 bfs 구조로 구현

 

5. Github