[너비우선탐색#1] 백준 2178번: 미로 탐색 JAVA

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

 

 

출력

---

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

 

예제입출력

---

 

 

풀이

---

 이번 문제는 너비우선탐색을 이용하면 쉽게 풀리는 문제이다. 이전의 그래프에서의 너비우선탐색 알고리즘과 달리 이번 문제에서는 2차원 배열상에서의 상,하,좌,우로 1칸식 움직임을 가져갈 수 있는 형태이다. 

 

 0은 갈 수 없는 좌표이고 1은 이동할 수 있는 좌표이다. 각 좌표를 방문 후 각 좌표의 값을 1씩 증가시켜주면서 이동하면 최종적으로 n, m좌표까지의 이동한 칸의 개수를 알 수 있다. 물론 방문 여부도 체크 해줘야한다. [아래 그림 참고]

 

4 6 (변환 전)                 4 6 (변환 후)

1 0 1 1 1 1                   1 0 9 10 11 12

1 0 1 0 1 0                   2 0 8 0 12 0

1 0 1 0 1 1                   3 0 7 0 13 14

1 1 1 0 1 1                   4 5 6 0 14 15

 

 

소스코드

---

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

public class Main {
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[][] graph = new int[n+1][m+1];
		boolean[][] visited = new boolean[n+1][m+1];
		
		for(int i=1; i<n+1; i++) {
			String[] str = br.readLine().split("");
			
			for(int j=1; j<m+1; j++)
				graph[i][j] = Integer.parseInt(str[j-1]);
		}
		
		
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1}; // 왼쪽, 오른쪽, 위, 아래
		
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(1, 1));
		visited[1][1] = true;
		
		while(!q.isEmpty()) {
			
			Point point = q.poll();
			
			for(int i=0; i<4; i++) {
				
				int mx = point.x + dx[i];
				int my = point.y + dy[i];
				if(mx>0 && mx<m+1 && my>0 && my<n+1) {
					
					if(graph[my][mx] != 0 && visited[my][mx]==false) {
						visited[my][mx] = true;
						graph[my][mx] = graph[point.y][point.x] + 1;
						q.offer(new Point(mx, my));
					}
				}
			}
		}
		bw.write(String.valueOf(graph[n][m]));
		bw.flush();
		bw.close();
		
	}
	
	static class Point{
		int x;
		int y;
		
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
}