백준 14940번 : 쉬운 최단거리

 문제

www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

14940 쉬운 최단거리

 

 구현 방법

 최단 거리를 구해야 하기 때문에 bfs를 통해 구현하였습니다.

목표 지점을 시작으로 각 depth를 구해주면 목표지점까지의 거리가 됩니다.

방문체크로 map을 0으로 바꿔준 후 bfs 가 끝나고 map을 탐색했을 때 1이 남아있으면 벽으로 인해 도달하지 못한 위치로 해당 위치를 -1로 바꿔줍니다.

 

 구현 코드

package BOJ.Gold;

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

public class BOJ14940_쉬운최단거리 {
	static int R, C;
	static int[][] map, ans, deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<move> queue;
	static class move {
		int r, c, cnt;

		public move(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}
	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();
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		ans = new int[R][C];
		queue = new LinkedList<>();
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
				if(map[r][c]==2) {
					map[r][c] = 0;
					queue.offer(new move(r, c, 0));
				}
			}
		}
		// 입력완료
		
		bfs();
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (map[r][c]==1) ans[r][c]=-1; // 도달하지 못한 위치면 -1로 바꿔줌
				sb.append(ans[r][c]+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	static void bfs() {
		while(!queue.isEmpty()) {
			int size = queue.size();
			for (int i=0;i<size;i++) { // 각 depth 만큼 반복문 돌리기
				move now = queue.poll();
				ans[now.r][now.c] = now.cnt;
				for (int d=0;d<4;d++) {
					int nr = now.r+deltas[d][0];
					int nc = now.c+deltas[d][1];
					if (isIn(nr, nc) && map[nr][nc]==1) {
						map[nr][nc] = 0; // 방문처리
						queue.offer(new move(nr, nc, now.cnt+1)); 
					}
				}
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!