2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
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를 작성해보았습니다.
이 문제를 풀 때 아래의 블로그를 참고해서 풀었습니다.
[자바] 백준 2178번 미로 탐색
안녕하세요- 1일 1코딩 1포스팅!벌써 세번째네요 :)작심삼일이 되진 않겠습니다! 화또화또백준 2178번 미...
blog.naver.com
'프로그래밍 문제 > BOJ(백준 온라인 저지)' 카테고리의 다른 글
[BOJ 7576번] 토마토(JAVA) (0) | 2020.09.23 |
---|---|
백준 3052 / C / 나머지 / * (0) | 2020.09.23 |
백준 2577 / 숫자의 개수 / C / * (0) | 2020.09.22 |
[BOJ 1012번] 유기농 배추(C++) (0) | 2020.09.21 |
백준 2562 / 최대값 / C / * (0) | 2020.09.21 |