[백준/자바] 2178번: 미로 탐색

문제

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

풀이

• N * M 크기 배열로 표현되는 미로
• 1은 이동 가능한 칸, 0은 이동 불가능한 칸
• 미로가 주어졌을 때, (1, 1)에서 (n, m)로 이동할 때 지나야 하는 최소 칸 수 출력

전형적인 BFS 문제 입니다.
모든 칸을 지난 후 (n, m)에 저장된 이동횟수를 출력하면 됩니다.

		map = new int[n][m];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}

• 미로의 정보를 2차원 배열에 저장합니다.
• 여기서 미로의 정보는 공백을 기준으로 주어진 것이 아닌 문자열 하나로 주어졌기 때문에, charAt() 메서드를 사용해 미로의 정보를 하나씩 저장합니다.

	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { 0, 0 }); // 시작 지점 삽입
		dist = new int[n][m];
		dist[0][0] = 1; // 시작 지점 이동 칸 수 삽입

• queue에 시작 지점인 (0, 0)을 삽입합니다.
• 이동횟수를 2차원 배열에 넣을 것이기 때문에, 시작 지점에 이동한 칸의 횟수인 1을 초기화해 줍니다.

		while (!queue.isEmpty()) {
        	// 현재 탐색한 좌표 (r, c)
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			
            // 4방 탐색
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
                // 범위를 넘어가면 pass
				if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                // 이동할 수 없는 칸이거나 이미 방문한 좌표라면 pass
				if (map[nr][nc] == 0 || dist[nr][nc] != 0) continue;
				
                // 위 조건과 만족하지 않다면, 현재 좌표 + 1을 이동할 좌표에 삽입
                // 다음 좌표 삽입
				dist[nr][nc] = dist[r][c] + 1;
				queue.add(new int[] { nr, nc });
			}
		}
	}

• 이후 4방 탐색을 진행하여 이동할 수 있는 좌표를 모두 탐색해 줍니다.
• 탐색을 마쳤으면, 마지막에 (n, m) 좌표의 값을 출력하면 끝

코드

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

public class Main_2178 {
	static int n, m;
	static int[][] map, dist;
	
	static final int[] dr = { -1, 1, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1 };
	
	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { 0, 0 });
		dist = new int[n][m];
		dist[0][0] = 1;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
				if (map[nr][nc] == 0 || dist[nr][nc] != 0) continue;
				
				dist[nr][nc] = dist[r][c] + 1;
				queue.add(new int[] { nr, nc });
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		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];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}
		
		bfs();
		
		System.out.println(dist[n-1][m-1]);
	}
}