[백준2178] 미로 탐색 / Java

링크 | https://www.acmicpc.net/problem/2178

문제 |

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

Solution |

• 너비우선탐색(BFS) 이용.

• BFS를 이용하되 최단 거리를 구하는 것이므로 지나온 좌표의 개수를 maze에 누적하여 더해준다. 방문한 좌표는 1이상의 값을 가지고 지나기자 못하는 길은 0값을 가지므로 좌표가 1인 곳만 확인하면 되므로 vistied 부울 배열을 이용하지 않아도 된다.

• 움직일 수 있는 상하좌우를 반복문을 이용하여 넣어준다.
  int[] dx = {0, 0, -1, 1};
  int[] dy = {1, -1, 0, 0};

• 최소 칸 수 = maze[N][M]

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

public class Maze {
	static int N, M;
	static int[][] maze;
	static LinkedList<Integer> queue = new LinkedList<Integer>();
			
	public static void main(String[] args) throws IOException {
		String str;
		String[] splitStr;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));			
		StringTokenizer s = new StringTokenizer(br.readLine());
		N = Integer.parseInt(s.nextToken()); //행
		M = Integer.parseInt(s.nextToken()); //열

		maze = new int[N+1][M+1];
		for (int i=1; i<=N; i++) {
			str = br.readLine();
			splitStr = str.split("");

			for (int j=1; j<=M; j++) {				
				maze[i][j]=Integer.parseInt(splitStr[j-1]);
			}
		}
		
		SearchMaze(1, 1); 		
		System.out.println(maze[N][M]);

	}
	
	static void SearchMaze(int x, int y) {
		int nx, ny;
		//좌표값의 상하좌우 비교
		int[] dx = {0, 0, -1, 1};
		int[] dy = {1, -1, 0, 0};
		
		queue.add(x);
		queue.add(y);

		while (!queue.isEmpty()) {
			x=queue.pollFirst();
			y=queue.pollFirst();

		    for (int i=0; i<4; i++) {
		    	nx = x +dx[i];
		    	ny = y +dy[i];
		        if (nx>=1 && nx<=N && ny>=1 && ny<=M ){ 
		        	if (maze[nx][ny]==1) {
		        		maze[nx][ny] += maze[x][y];
		        		queue.add(nx);
		        		queue.add(ny);
		        	}  
		        }
		    }
		}
	}
}