[백준]2178_미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

---

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

---

출력

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

---

예제 입력

4 6
101111
101010
101011
111011

예제 출력

15

---

풀이

(0,0)에서 출발해 (N,M)까지 도달하는데 얼마나 걸렸는지 구하는 문제로 BFS를 적용할 수 있는 문제이다.
문자열을 char형으로 변환해 배열에 넣는 .toCharArray()와 숫자 형태의 char형을 int형으로 반환하는 .getNumericValue()를 사용하였다.

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

public class Main {
	static int N, M, cnt;	
	static boolean[][] visited;
	static int[][] arr;
	
	//이동좌표 우 왼 하 상
	static int[] moveX = {0, 0, 1, -1};
	static int[] moveY = {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());

		arr = new int[N][M];
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			char[] ch = str.toCharArray(); // 문자열 받아서 문자배열로 반환
			for (int j = 0; j < ch.length; j++) {
				arr[i][j] = Character.getNumericValue(ch[j]); //받은 문자를 char타입으로 변환
			}
		}
		visited[0][0] = true; // 출발지 항상 0,0임
		bfs(0, 0); //시작
		
		System.out.println(arr[N-1][M-1]);

	}

	public static void bfs(int x, int y) {
		Queue<spot> q = new LinkedList<>();
		q.add(new spot(x, y));
		while(!q.isEmpty()) {
			spot s = q.poll();
			for(int i = 0; i<4; i++) {
				int nextX = s.x + moveX[i];
				int nextY = s.y + moveY[i];
				// 이동할 칸이 0으로 막혀있거나 범위에서 벗어나는 경
				if(nextX < 0 || nextY <0 || nextX>= N || nextY >=M) {
					continue;
				}
				//방문한적이 있거나, 0으로 막혀있는 경
				if(visited[nextX][nextY]||arr[nextX][nextY] == 0) {
					continue;
				}
			q.add(new spot(nextX, nextY));
			arr[nextX][nextY] = arr[s.x][s.y] + 1; //0부터 시작했으니 +1 해주기 
			visited[nextX][nextY] = true;
			}
		}
	}
}

class spot {
	int x;
	int y;
	
	spot(int x, int y){
		this.x = x;
		this.y = y;
	}
}

• 동서남북을 지나며 1인 칸만 지나갈 수 있도록 하기위해 각 지점의 좌표를 확인할 수 있는 class spot을 작성하였다.
• (0,0)부터 출발하니 spot(0,0)으로 설정하고 큐에서 빼온 s를 동서남북으로 확인해준다.
• 만약 주어진 범위에서 벗어나면 continue를 통해 다음 방향으로 갈 수 있도록 전환해주었다.
• 이미 방문했거나 가려는 방향이 0으로 막혀있다면 continue를 통해 다음 방향으로 갈 수 있도록 전환해주었다.
• 모든 if문을 통과했다면, 큐에 해당 좌표를 추가하고 arr값에 +1을 해준다 (시작하는 칸부터 1칸으로 생각하고 출발하니깐)
• 방문한 좌표는 true로 바꿔준다.
  
  코드를 실행하면 arr에 이런 값이 들어가게 될 것이다.