코드
import java.util.*;
class 미로의차단거리통로BFS {
static int[] dx={-1, 0, 1, 0};
static int[] dy={0, 1, 0, -1};
static int[][] board, dis;
static int cnt = 0;
static int answer = Integer.MAX_VALUE;
static void BFS(int x, int y){
Queue<Point> Q=new LinkedList<>();
Q.offer(new Point(x, y));
board[x][y]=1;
while(!Q.isEmpty()){
Point tmp=Q.poll();
for(int i=0; i<4; i++){
int nx=tmp.x+dx[i];
int ny=tmp.y+dy[i];
if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
board[nx][ny]=1;
Q.offer(new Point(nx, ny));
dis[nx][ny]=dis[tmp.x][tmp.y]+1;
}
}
}
}
static void BFS3(int x,int y) {
Queue<Point> q = new LinkedList<Point>();
q.offer(new Point(x, y));
board[x][y]=1;
while(!q.isEmpty()) {
int size = q.size();
//Q 순회용
for (int i = 0; i < size; i++) {
Point p = q.poll();
// Q 요소의 다음 갈 곳 순회용
for (int j = 0; j < dx.length; j++) {
int nx = p.x+dx[j]; //다음갈 곳
int ny = p.y+dy[j];
if(nx>=1&&nx<=7 && ny>=1&&ny<=7 &&board[nx][ny]==0) {
board[nx][ny] = 1;
dis[nx][ny] = dis[p.x][p.y]+1;
q.offer(new Point(nx, ny));
}
}
}
}
}
public static void main(String[] args){
dis=new int[8][8];
//인덱스 [0][n], [n][0]은 버리는 공간, 1부터 시작을 위함
int[][] arr =
{ {0, 0, 0, 0, 0, 0, 0, 0}
/*-----------------------*/
, {0,/**/ 0, 0, 0, 0, 0, 0, 0}
, {0,/**/ 0, 1, 1, 1, 1, 1, 0}
, {0,/**/ 0, 0, 0, 1, 0, 0, 0}
, {0,/**/ 1, 1, 0, 1, 0, 1, 1}
, {0,/**/ 1, 1, 0, 0, 0, 0, 1}
, {0,/**/ 1, 1, 0, 1, 1, 0, 0}
, {0,/**/ 1, 0, 0, 0, 0, 0, 0} };
board = arr.clone();
BFS3(1, 1);
for(int[] y : dis) {
for (int x : y) {
System.out.printf("%2s ", x);
}
System.out.println();
}
if(dis[7][7]==0) System.out.println(-1); //목적지 도달 불가
else System.out.println(dis[7][7]);
}
}
class Point{
public int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return x+":"+y;
}
}결과
0 0 0 0 0 0 0 0
0 0 1 2 3 4 5 6
0 1 0 0 0 0 0 7
0 2 3 4 0 10 9 8
0 0 0 5 0 9 0 0
0 0 0 6 7 8 9 0
0 0 0 7 0 0 10 11
0 0 9 8 9 10 11 12
12최단 거리는 DFS가 아닌 BFS를 쓰는 것이 맞다.
DFS도 가능하지만 모든 경우의 수를 끝까지 탐색해야만 최단 거리임을 보증할 수 있다.
반면에 BFS는 가장 먼저 발견한 것이 최단거리임을 보장한다.
