/ BOJ

BOJ_2178_미로탐색_JAVA

문제 : 미로탐색

링크 : BOJ_2178_미로탐색

접근 방식

오늘 앞서 풀었던 아기 상어 문제에 있는 최단 거리를 구하는 BFS의 알고리즘을 그대로 사용해서 풀 수 있었다. 배열의 시작점부터 끝까지 BFS으로 탐색하면서 가장 먼저 목적지까지 도달하는 순간 그때의 거리를 출력하면 해결할 수 있다.

풀이 방법

  1. 값을 읽어와 N*M 크기의 배열을 생성한다.

  2. 방문정보를 저장할 동일한 크기의 boolean 배열도 생성한다.

  3. 배열에 값을 읽어와 저장하고, BFS를 호출한다.

  4. BFS에서 사방탐색을 통해 이동할 수 있는 경우를 확인하고, 방문하지 않은 곳이면서 이동이 가능할 경우 이동한다. 배열에서 벽이 0이므로, 0이 아닐경우 또는 1일경우 이동가능한 것으로 본다.

  5. 탐색 도중 목적지에 도달한 최초 거리를 출력하고 return 한다.

소스 코드


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 BOJ_2178_미로탐색 {


	static char[][] arr;
	static boolean[][] isVisited;
	static int N,M;
	static int[][] dir = { {1,0},{-1,0},{0,1},{0,-1} };
	static int cnt;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine()," ");

		N = Integer.parseInt(st.nextToken());

		M = Integer.parseInt(st.nextToken());
		arr = new char[N][M];
		isVisited = new boolean[N][M];
		for(int i=0;i<N;i++) {
			arr[i] = in.readLine().toCharArray();
		}

		bfs(0,0);		


	}

	static void bfs(int x, int y) {

		Queue<int[]> queue = new LinkedList<>();

		queue.offer(new int[]{x,y,0});

		isVisited[x][y] = true;

		while(!queue.isEmpty()) {


			int[] pos = queue.poll();
			if(pos[0] == N-1 && pos[1] == M-1) {
				System.out.println(++pos[2]);
				break;
			}
			for(int d=0;d<4;d++) {
				int dx = pos[0] + dir[d][0];
				int dy = pos[1] + dir[d][1];
				if(dx >= 0 && dx < N && dy >= 0 && dy < M) {
					if(arr[dx][dy] == '1' && isVisited[dx][dy] == false) {
						isVisited[dx][dy] = true;
						queue.offer(new int[] {dx,dy,pos[2]+1});
					}
				}
			}

		}



	}

}