[JAVA][백준] 2178. 미로 탐색

🔗링크

https://www.acmicpc.net/problem/2178

---

📑문제

---

🤔접근 방법

• 처음엔 dfs로 풀어야 한다고 생각해서 재귀할 때마다 res에 값을 1씩 추가해줬다. 그랬더니 모든 1에서 다 카운트가 돼서 1의 개수가 다 출력됐다.

• 그래서 인접행렬을 사용한 bfs로 코드를 짰다. 근데 예제 출력이 한문제만 틀려서 이리저리 고치다가 사방탐색하는 dr, dc의 방향 순서를 우하좌상에서 상하좌우로 바꿨더니 틀렸던 예제는 맞고 맞았던 예제는 틀렸다.

• 뭐가 문제인지 잘 모르겠어서 구글링을 해봤더니 다 큐로 푼 코드밖에 없었다... 오기가 생겨서 계속 붙잡고 있다가 오늘 못자겠구나 싶어서 코드 다시 짰다... ㅠ ㅠ

• 진작에 큐로 만들걸.. 막상 다시 시작하니까 많이 고민 안하고 Node 클래스 만들어서 금방 풀었다!

• 그리고 사소하지만 한가지 뿌듯했던건 이제 공백 없이 문자열로 입력받아도 막힘 없이 배열에 저장할 수 있는 거! 2주 전까지만 해도 당황하면 split도 제대로 못쓰고 substring은 있는지도 몰랐는데 이제는 둘 다 확실하게 사용할 수 있다.. 희희 더 발전해야지.

---

🗝️코드

정답코드

package boj;

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 Boj_2178_미로탐색 {

	public static class Node {
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static int N, M, res;
	static int[][] map, dist;
	static boolean[][] visited;
	// 상 하 좌 우
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	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());

		map = new int[N][M];
		dist = new int[N][M];
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(str.substring(j, j + 1));
			}
		} // 미로 정보 입력

		// 0 : 벽, 1 : 길
		dist[0][0] = 1;
		visited[0][0] = true; // 시작지점 방문체크
		bfs(0, 0);
		System.out.println(dist[N - 1][M - 1]);

	}// main

	static void bfs(int r, int c) {

		Queue<Node> queue = new LinkedList<>();

		queue.add(new Node(r, c)); // 큐에 현재 지점 넣어주기

		// 큐가 비지 않는 동안 반복
		while (!queue.isEmpty()) {

			Node now = queue.poll(); // 큐에서 하나 빼서

			// 델타탐색
			for (int i = 0; i < 4; i++) {

				int nr = now.x + dr[i];
				int nc = now.y + dc[i];

				// 범위 안에 들어오고 방문 안했고 다음 목적지가 길이라면
				if (nr >= 0 && nr < N && nc >= 0 && nc < M && !visited[nr][nc] && map[nr][nc] == 1) {
					queue.add(new Node(nr, nc)); // 큐에 넣어주기
					visited[nr][nc] = true; // 방문체크
					dist[nr][nc] = dist[now.x][now.y] + 1;

				}

			}

		} // while

	}// bfs

}

인접행렬로 짰던 코드

package boj;

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

public class Boj_2178_미로탐색 {

	static int N, M, res;
	static int[][] map, dist;
	static boolean[][] visited;
	// 상 하 좌 우
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	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());

		map = new int[N][M];
		dist = new int[N][M];
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(str.substring(j, j + 1));
			}
		} // 미로 정보 입력

		// 0 : 벽, 1 : 길
		dist[0][0] = 1;
		bfs(0, 0);
		System.out.println(dist[N - 1][M - 1]);

	}// main

	static void bfs(int r, int c) {

		visited[r][c] = true; // 시작지점 방문체크

		for (int i = 0; i < 4; i++) {

			int nr = r + dr[i];
			int nc = c + dc[i]; // 내가 다음에 방문할 곳

			// 배열의 범위를 벗어나지 않고 방문처리 안되어있고 벽이 아닐 때
			if (nr >= 0 && nr < N && nc >= 0 && nc < M && !visited[nr][nc] && map[nr][nc] == 1) {
				dist[nr][nc] = dist[r][c]+1;
				visited[nr][nc] = true;
				bfs(nr, nc);

			}

		}

	}// bfs

}