[백준-2178번 자바/java] 미로 탐색 _디버깅의 눈물
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
미로 탐색 성공
| 1 초 | 192 MB | 133988 | 57340 | 36898 | 41.518% |
문제
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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력 1 복사
4 6
101111
101010
101011
111011
예제 출력 1 복사
15예제 입력 2 복사
4 6
110110
110110
111111
111101
예제 출력 2 복사
9
예제 입력 3 복사
2 25
1011101110111011101110111
1110111011101110111011101
예제 출력 3 복사
38
예제 입력 4 복사
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
예제 출력 4 복사
13
체크 포인트
1. BFS(너비 우선 탐색)를 이용하는 문제
-DFS(깊이 우선 탐색)을 이용하는 경우, 최단 거리를 탐색하는 것이 아니기 때문에 비효율적이다. 또한 이 문제에서는 시간초과를 야기할 수 있어서 올바른 풀이가 아니다.
-BFS의 경우에는 시작 노드(1,1)로부터, 해당 노드와 직접 연결된 노드들을 먼저 탐색한다. 이에 따라 최단 거리를 구하는 위와 같은 문제에서 사용하면 효율적이다.
2. 이동한 칸 수를 카운팅하는 부분을 생각하면서 시간이 다소 소요되었다.
-기본적으로 최단 거리를 향해 한칸 이동할 때마다 카운팅 수가 하나 늘어나야한다.
-한칸 이동할 때마다 이전 칸에 입력된 숫자+1을 해주는 방식으로 해결했다.
-이 외의 방법으로는 Q에 새로운 x, y(nx,ny)가 입력될 때마다 따로 카운팅 변수를 지정해서 해결할 수도 있을 것이라고 본다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 너비, 높이
static int N, M;
// 미로가 존재하는 지도 배열
static int[][] map;
// 지도 상의 방문한 곳 정보를 담아주는 배열
static boolean[][] visited;
// 상/하/좌/우 탐색
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};
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());
// 지도 배열 초기화. N+1을 해준 이유는 0,0이 아니라 1,1부터 표시해주기 위함입니다.
map = new int[N+1][M+1];
// 지도 배열에 값 입력
for(int i=1; i<=N; i++){
st = new StringTokenizer(br.readLine());
String[] s = st.nextToken().split("");
for(int j=1; j<=M; j++){
map[i][j] = Integer.parseInt(s[j-1]);
}
}
// 입력된 값을 확인하기 위한 부분
/* for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){
if(j==M){
System.out.println(map[i][j] + " ");
}
else{
System.out.print(map[i][j] + " ");
}
}
}*/
// 방문 정보 배열 초기화
visited = new boolean[N+1][M+1];
// bfs 1,1부터 시작!
bfs(1,1);
// 결과 출력(마지막 걸음이 닿은 곳)
System.out.println(map[N][M]);
}
public static void bfs(int x, int y){
Queue<Integer> Q = new LinkedList<Integer>();
// 해당 (x,y) 방문 처리
visited[x][y] = true;
// x,y 값 입력
Q.add(x);
Q.add(y);
// bfs 탐색
while(!Q.isEmpty()){
x = Q.poll();
y = Q.poll();
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 새로운 (nx,ny)를 기준으로 상,하,좌,우가 지도 상 위의 점이고,
if(nx>=0 && ny>=0 && nx<N+1 && ny<M+1){
// 이 점을 방문한 적이 없고, 이 점이 이동할 수 있는 길(1) 위라면 탐색 진행,
if(!visited[nx][ny] && map[nx][ny]==1){
// 다음 탐색을 위한 새로운 (nx,ny) 추가
Q.add(nx);
Q.add(ny);
// 미로위의 길을 지나갈 때마다, 이전 칸의 숫자보다 한칸 추가
map[nx][ny] = map[x][y] + 1;
}
}
}
}
}
}