14940번 - 쉬운 최단거리

1️⃣ BFS

 

✏️ 풀이 과정

최단거리 문제이지만 다익스트라 알고리즘보다 BFS를 이용하는 것이 훨씬 경제적입니다.

 

기본적인 아이디어는 큐의 사이즈를 통해 단계를 구분하는 BFS를 통해 2인 지점으로부터 한 단계 뻗어나갈 때마다 거리가 1씩 늘어나는 것으로 해석하는 것입니다.

 

불필요한 메모리 공간 이용이나 중복 계산을 막기 위해서 입력으로 받은 이차원 배열을 그대로 방문 여부를 표시하는 데 이용하고 입력을 받을 때 기본적으로 1을 -1로 받았다가(2는 BFS 시작을 위해 큐에 넣고 0으로 만듭니다.) BFS를 진행하면서 거리 값으로 바꿔주는 것입니다.(-1인 위치는 미방문이기 때문에 방문 여부를 알 수 있습니다.) 탐색이 완료되면 연결되어있지 않은 좌표의 경우 그대로 -1으로 남아있기 때문에 문제의 조건을 만족할 수 있습니다. BFS를 돌린 이후 해당 배열을 그대로 출력해주면 문제가 해결됩니다.

 

💻 코드

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

public class Main {
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	static class Point {
		int r;
		int c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	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 input, nr, nc, size, cnt = 0;
		LinkedList<Point> q = new LinkedList<>();
		Point cur;
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;j++) {
				input = Integer.parseInt(st.nextToken());
				if(input == 2) {
					q.offer(new Point(i, j));
					map[i][j] = 0;
				} else {
					map[i][j] = -1 * input;
				}
			}
		}
		while(!q.isEmpty()) {
			size = q.size();
			cnt++;
			for(int k=0;k<size;k++) {
				cur = q.poll();
				for(int i=0;i<4;i++) {
					nr = cur.r + dr[i];
					nc = cur.c + dc[i];
					if(nr>=0 && nc>=0 && nr<n && nc<m && map[nr][nc] == -1) {
						q.offer(new Point(nr, nc));
						map[nr][nc] = cnt;
					}
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				sb.append(map[i][j]+" ");
			}
			sb.append("\n");
		}
		System.out.print(sb);
		br.close();
	}
}