백준_2178번_미로탐색(자바)

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

2178번: 미로 탐색

 

해당 문제는 BFS,DFS로 모두 풀이 할 수 있으나, DFS로 풀이 했을경우 시간초과가 발생하므로, BFS로 풀이 하였습니다.

[ DFS 풀이 방법도 주석으로 남겨 놓았습니다.]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

//4 6
//101111
//101010
//101011
//111011


public class Main {

static int n;
static int m;
static int[][] map;
static boolean[][] chx;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};

static int result;


public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());

map = new int[n][m];
chx = new boolean[n][m];

for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < m; j++) {
map[i][j] = s.charAt(j) - '0';
}
}

// result = Integer.MAX_VALUE;
// dfs(0,0,1);
// System.out.println(result);


chx[0][0] =true;
bfs(0,0);
System.out.println(map[n-1][m-1]);


}

// public static void dfs(int x, int y, int cnt){
// if(x == n-1 && y == m-1){
// result = Integer.min(result,cnt);
// return;
// }
//
// if(cnt > result) return;
//
// if(x>0&&!chx[x-1][y]&&map[x-1][y]==1){
// chx[x-1][y]= true;
// dfs(x-1,y,cnt+1);
// chx[x-1][y]=false;
// }
// if(x<n-1&&!chx[x+1][y]&&map[x+1][y]==1){
// chx[x+1][y]= true;
// dfs(x+1,y,cnt+1);
// chx[x+1][y]=false;
// }
// if(y>0&&!chx[x][y-1] && map[x][y-1]==1){
// chx[x][y-1]= true;
// dfs(x,y-1,cnt+1);
// chx[x][y-1]=false;
// }
// if(y<m-1&&!chx[x][y+1]&&map[x][y+1]==1){
// chx[x][y+1]= true;
// dfs(x,y+1,cnt+1);
// chx[x][y+1]=false;
// }
// }

public static void bfs(int x , int y){
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {x,y});

while (!q.isEmpty()){
int[] now = q.poll();
int nowX = now[0];
int nowY = now[1];

for (int i = 0; i < 4; i++) {
int nextX = nowX+dx[i];
int nextY = nowY+dy[i];

if(nextX < 0 || nextY < 0|| nextX > n-1 || nextY > m-1 || chx[nextX][nextY] ||map[nextX][nextY]==0) continue;

q.add(new int[] {nextX,nextY});
map[nextX][nextY] = map[nowX][nowY] +1;
chx[nextX][nextY] =true;
}
}
}

}