[BOJ/백준] 14940번 쉬운 최단 거리 (JAVA/자바) - BFS

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

14940번: 쉬운 최단거리

 

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

문제를 꼼꼼히 읽어야 겠다고 생각했던 부분.. 이걸 고려 하지 않아서 처음에 실패했다..

 

---

풀이

1. 간단한 bfs 탐색

2. 목적지를 시작점으로 잡고 목적지부터 다른 노드들까지의 거리를 dist에 저장

	public static void bfs() {
		Queue<Point> Q = new LinkedList<>();
		Q.add(start);
		dist[start.i][start.j]=0;
		
		while(!Q.isEmpty()) {
			Point cur = Q.poll();
			
			for(int d=0; d<4; d++) {
				int ni = cur.i + di[d];
				int nj = cur.j + dj[d];
				
				if(ni<0 || nj<0 || ni>=N || nj>=M) continue;
				if(dist[ni][nj] != -1) continue;
				if(map[ni][nj] == 0) continue;

				dist[ni][nj] = dist[cur.i][cur.j]+1;
				Q.add(new Point(ni, nj));
			}
		}
	}

3. 출력 시 방문하지 않았고, 원래 가지 못하는 노드라면 "0"을 출력하도록 분기 설정

		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(dist[i][j]==-1 && map[i][j] !=1) sb.append(0).append(" ");
				else sb.append(dist[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());

 

전체 코드

package bdfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_14940_쉬운최단거리 {
	static class Point {
		int i, j;

		Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}

	static int[] di = { 0, 0, 1, -1 };
	static int[] dj = { 1, -1, 0, 0 };
	static int[][] map, dist;
	static int N, M;
	static Point start;

	public static void main(String[] args) throws Exception {
		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];
		dist = new int[N][M];
		for(int i=0; i<N; i++) {
			Arrays.fill(dist[i], -1);
		}
		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 = new Point(i, j);
				}
			}
		}
		
		bfs();
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(dist[i][j]==-1 && map[i][j] !=1) sb.append(0).append(" ");
				else sb.append(dist[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
		
	}
	
	public static void bfs() {
		Queue<Point> Q = new LinkedList<>();
		Q.add(start);
		dist[start.i][start.j]=0;
		
		while(!Q.isEmpty()) {
			Point cur = Q.poll();
			
			for(int d=0; d<4; d++) {
				int ni = cur.i + di[d];
				int nj = cur.j + dj[d];
				
				if(ni<0 || nj<0 || ni>=N || nj>=M) continue;
				if(dist[ni][nj] != -1) continue;
				if(map[ni][nj] == 0) continue;

				dist[ni][nj] = dist[cur.i][cur.j]+1;
				Q.add(new Point(ni, nj));
			}
		}
	}
}