미로 탐색
문제 설명
N×M크기의 배열로 표현되는 미로가 있다.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
제한 사항
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
4 6
101111
101010
101011
111011
출력
15
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
풀이
- BFS탐색으로 탐색한 지점의 경로수를 + 해 배열에 저장하면서 진행한다.
푸는 과정에서의 오류
BFS알고리즘의 이해가 부족해, 재귀호출로 BFS를 해결하려 했습니다. 큐에 저장되어있는것을 활용하면 되기에 재귀는 필요없을거라 생각하여, 반복문으로 큐가 빌때까지 돌려 문제를 해결하였습니다.
배운점
BFS, DFS의 차이를 이해할수 있었고, 이를 기초적으로 활용할수 있는 법을 배운 문제였습니다.
소스코드
package MazeSearch;
import java.awt.Point;
import java.util.*;
public class MazeSearch {
private static Queue<Point> q = new LinkedList<>();
private static int xMax;
private static int yMax;
private static int[] dx = {-1,1,0,0};
private static int[] dy = {0,0,-1,1};
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
String[] mapSize = sc.nextLine().split("\\s");
xMax = Integer.parseInt(mapSize[0]);
yMax = Integer.parseInt(mapSize[1]);
int answer =0;
int[][] map = new int[xMax][yMax];
//입력부
for(int i=0;i<xMax;i++) {
String[] tmp = sc.nextLine().split("");
for(int ii=0;ii<yMax;ii++) {
map[i][ii] = Integer.parseInt(tmp[ii]);
}
}
//bfs 처리
q.offer(new Point(0,0));
bfs(map);
System.out.println(map[xMax-1][yMax-1]);
}
public static void bfs(int[][] map) {
while(!q.isEmpty()) {
for(int i=0;i<4;i++) {
int nextX = q.peek().x + dx[i];
int nextY = q.peek().y + dy[i];
if(nextX < 0 || nextY < 0 || nextX >= xMax || nextY >= yMax) {
continue;
}
if(map[nextX][nextY] != 1) {
continue;
}
map[nextX][nextY] = map[q.peek().x][q.peek().y] + 1;
q.offer(new Point(nextX,nextY));
}
q.poll();
}
}
}