[2178번] 미로 탐색 ( bfs, substring(), queue 2차원 배열 )

---

---

✅ 문제 이해

• 이 문제는 최대 데이터 크기가 100 으로 작기 때문에 시간 제한을 별도로 생각하지 않아도 된다.

• 문제의 요구사항은 지나야 하는 칸의 수의 최솟값을 찾는 문제이다.
  이는 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 발견하는지를 구하는 것과 동일하다.

• dfs, bfs를 모두 사용해도 가능하다.
  하지만, dfs는 해당 깊이까지 다 들어간 후 다시 나오는 과정을 반복하고
  bfs는 이전 깊이에서 갈 수 있는 노드 탐색을 다 마친 후 해당 깊이로 넘어가므로
  bfs를 사용하여 해당 깊이에 최초로 도달했을 때의 깊이를 바로 출력하는 것이 더 적합하다는 판단이 선다.

손으로 그려보면 더 쉽게 이해할 수 있다.

문제를 예로 들어서 전체 과정을 그려보자.

노드 숫자인 1을 depth 숫자로 바꿔주면 더 편리하게 풀 수 있다.
이 발상은 시작점에서 자기 자신까지의 최단 거리를 나타내는 것이다.
따라서, 나중에 '시작점에서 7 만큼 이동했을 때 갈 수 있는 노드는 어디인가요?' 라는 문제에 쉽게 답할 수 있다.

---

✅ Bfs

큐를 사용한다.
전체적인 동작과정은 dfs와 같지만, 큐는 선입선출이므로 방문 순서가 달라진다.

인접 리스트

손으로 그려보자.

---

👾 주의

Queue<int[]> queue = new LinkedList<>();

// {3, 7}
int now[] = queue.poll();

// now[0] = 3, and now[1] = 7
int x = now[0]; //x좌표
int y = now[1]; //y좌표

---

✅ 코드

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 arr[][];
	static boolean visited[][];
	//아래쪽 오른쪽 위쪽 왼쪽
	static int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
	static int n, m;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		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 s = br.readLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(s.substring(j, j + 1));
			}
		}

		//시작점 입력 (0,0)
		bfs(0, 0);

		//입력값은 1부터 시작이므로
		System.out.println(arr[n - 1][m - 1]);
	}

	private static void bfs(int i, int j) {
		//데이터가 2개 들어오니까 int 배열로
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {i, j}); //큐에 데이터 삽입
		visited[i][j] = true; // 삽입한 데이터의 방문처리
		while (!queue.isEmpty()) { //queue가 안 비었을 때 까지
			int now[] = queue.poll(); //하나 꺼냄
			for (int k = 0; k < 4; k++) { //아래 오른쪽 위쪽 왼쪽 탐색
				int x = now[0] + dx[k];
				int y = now[1] + dy[k];
				if (x >= 0 && y >= 0 && x < n && y < m) { //배열 범위 안에서
                	//0이 아니고 방문을 안한 노드일 때
					if (arr[x][y] != 0 && !visited[x][y]) {
						visited[x][y] = true;
                        //1 증가시킨 depth값 삽입!
						arr[x][y] = arr[now[0]][now[1]] + 1; 
						queue.add(new int[] {x, y}); //다음 값 넣어줌
					}
				}
			}

		}

	}
}

---

---

✅ 재도전 코드

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 boolean visited[][];
	static int arr[][];
	static int N = 0, M = 0;

	//오하왼상
	static int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		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 s = br.readLine();
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(s.substring(j, j + 1)); //문자열 나누기에 주의!
			}
		}
		dfs(0, 0);
		System.out.println(arr[N - 1][M - 1]);
	}

	private static void dfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {x, y});
		visited[x][y] = true;

		while (!queue.isEmpty()) {
			int now[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];
				if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
					if (!visited[nextX][nextY] && arr[nextX][nextY] != 0) {
						visited[nextX][nextY] = true;
						arr[nextX][nextY] = arr[now[0]][now[1]] + 1;
						queue.add(new int[] {nextX, nextY});
					}
				}
			}
		}
	}
}

---