[BOJ 2178번] 미로탐색(JAVA)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int N, M, cnt=0;
	static int[][] maze;
	static boolean[][] isVisit;
	static int dx[]= {0, 1, 0, -1};
	static int dy[]= {1, 0, -1, 0};
	
	public static void main(String args[]) throws Exception {
		String[] s=br.readLine().split(" ");
		N=Integer.parseInt(s[0]);
		M=Integer.parseInt(s[1]);
		maze=new int[N][M];
		isVisit=new boolean[N][M];
		for(int i=0;i<N;i++) {
			String s1=br.readLine();
			for(int j=0;j<M;j++) {
				maze[i][j]=(int)s1.charAt(j)-'0';
			}
		}
		bfs();
		System.out.println(maze[N-1][M-1]);
	}
	
	public static void bfs() {
		Queue<Integer> q_x=new LinkedList<>();
		Queue<Integer> q_y=new LinkedList<>();
		q_x.add(0);
		q_y.add(0);
		isVisit[0][0]=true;
		
		while(!q_x.isEmpty()) {
			int x=q_x.poll();
			int y=q_y.poll();
			for(int i=0;i<4;i++) {
				int temp_x=x+dx[i];
				int temp_y=y+dy[i];
				if(temp_x>=0&&temp_y>=0&&temp_x<N&&temp_y<M) {
					if(maze[temp_x][temp_y]==1&&isVisit[temp_x][temp_y]==false) {
						q_x.add(temp_x);
						q_y.add(temp_y);
						isVisit[temp_x][temp_y]=true;
						maze[temp_x][temp_y]=maze[x][y]+1;
					}
				}
			}
		}
	}
}

 

이 문제는 미로를 최소 경로로 탐색하는 문제입니다.

그렇기 떄문에 DFS로 탐색하기보다는 BFS로 탐색을 해보았습니다.

x좌표와 y좌표 값을 담는 두 개의 큐를 이용해서 BFS를 작성해보았습니다.

이 문제를 풀 때 아래의 블로그를 참고해서 풀었습니다.

m.blog.naver.com/PostView.nhn?blogId=lm040466&logNo=221787845393&proxyReferer=https:%2F%2Fwww.google.com%2F

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