[백준 BOJ/Silver I] 2178번 : 미로 탐색

 

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

2178번: 미로 탐색

 

dfs 문제는 여러번 풀어봤는데 bfs 문제는 마음속거리감이 심해서ㅠㅠㅋㅋㅋㅋㅋㅋㅋ 계속 피했었다 그래도 이제 bfs도 극복해야하기에 많이 풀어보려한다

방식은 dfs와 어느정도 비슷하면서 Queue를 이용한다는 점이 다른데 아직 익숙하지 않아서 여러번 읽어보며 익히려고 노력했다

우선 dfs 방식을 이용해서 풀어보았는데 이건 상하좌우 확인하며 끝까지 파고들기 때문에 최소의 칸을 구하기에는 효율적이지 않았고, 가까운 것들을 모두 확인하고 넘어가는 bfs 방식을 이용하여 최소의 칸을 구할 수 있었다

 

(0, 0) 에서 시작하기 때문에 먼저 큐에 담아준 후 제거하면서 상하좌우에 1로 표시된+아직 방문하지 않은 곳을 방문해서 해당 칸에 들어있는 수를 +1 해준다 이때 방문표시와 큐에 담아주는 과정을 거쳐야한다

이제 다시 큐에 담긴것을 하나씩 빼주면서 이전과 마찬가지로 상하좌우를 확인하며 1로 표시된+아직 방문하지 않은 곳을 방문해서 이전 칸에 있는 수보다 +1을 해주면 된다 이 과정들을 큐가 빌 때까지 반복해준다

 

이렇게 해서 마지막 (N-1, M-1) 까지 진행하면 몇번 확인하는 과정을 거쳤는지 알 수 있다 왜냐면 새롭게 가까운 상하좌우를 확인할때마다 칸의 수를 1씩 해주었기 때문에!!

즉 maze[N-1][M-1]의 값이 (0,0)부터 (N-1, M-1) 까지 이동할때 지나야하는 최소 칸의 수가 된다

 

최종 코드는 아래와 같다

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
	
	static int N;
	static int M;
	static int[][] maze;
	static boolean[][] visited;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		maze = new int[N][M];
		visited = new boolean[N][M];
		
		for(int i = 0; i < N; i++) {
			String[] str = sc.next().split("");
			for(int j = 0; j < M; j++) {
				maze[i][j] = Integer.parseInt(str[j]);
			}
		}
		
		bfs();
		System.out.println(maze[N-1][M-1]);
		
	}
	
	static void bfs() {
		Queue<int[]> q = new LinkedList<int[]>();
		
		visited[0][0] = true;
		q.add(new int[] {0, 0});
		
		while(!q.isEmpty()) {
			int[] xy = q.poll();
			int x = xy[0];
			int y = xy[1];
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx >=0 && nx < N && ny >= 0 && ny < M) { // 범위 벗어나지 않는지 확인
					if(maze[nx][ny] == 1 && !visited[nx][ny]) { // 이동할 수 있는 칸인지, 방문하지 않은 곳인지 확인
						visited[nx][ny] = true;
						q.add(new int[] {nx, ny});
						maze[nx][ny] = maze[x][y] + 1;
					}
				}
				
			}
			
		}
		
		
	}

}

 

큐에 넣고 빼면서 확인하는 과정들이 아직 완전 익숙하지는 않지만 비슷한 문제를 반복해서 풀면 흐름이 익숙해질거같다

 

최단거리를 구할때는 bfs방식을 이용하자!!!