[JAVA] 백준 알고리즘 2178 : 미로 탐색 (BFS)

빠른 경로 찾기

문제

소스

import java.util.*;

public class Main {

	// (dx,dy) : 우(0,1), 하(1,0), 좌(0,-1), 상(-1,0)
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	public static int n, m;
	public static int map[][]; // 미로
	public static boolean visit[][]; // 방문 표시를 위한 배열
		
	// 너비 우선 탐색 (BFS)
	public static void bfs(int x, int y) { // 시작 좌표 x,y
		Queue<Integer> qx = new LinkedList<Integer>();
		Queue<Integer> qy = new LinkedList<Integer>();
		
		qx.add(x);
		qy.add(y);
		
		while(!qx.isEmpty() && !qy.isEmpty()){
			x = qx.poll();
			y = qy.poll();
			visit[x][y] = true; // 방문 표시
			
			for (int i=0; i<4; i++){ // 오른쪽 아래 왼쪽 위 돌아가며 탐색
				int _x = x + dx[i]; // 0,1,0,-1
				int _y = y + dy[i]; // 1,0,-1,0
				
				if (_x >= 0 && _y >= 0 && _x < n && _y < m) {
					if(map[_x][_y] == 1 && visit[_x][_y] == false){ // 미방문
						qx.add(_x);
						qy.add(_y);
						visit[_x][_y] = true; // 방문 표시
						map[_x][_y] = map[x][y]+1; // 방문한 좌표는 이동 횟수로 변경
					}
				}
			}
		}
	}
	
	
	public static void main(String[] args) {	
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();

		map = new int[100][100];
		visit = new boolean[100][100];
		
		for (int i=0; i<n; i++) {
			String temp = sc.next();
			for (int j=0; j<m; j++) {
				map[i][j] = temp.charAt(j) - 48; // ASCII Code 48~57 (숫자) 문자를 숫자로 변환
			}
		}
		
		bfs(0 , 0); // bfs 시작
		System.out.print(map[n-1][m-1]);
	}
}

출처

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