[백준] 2178 미로 탐색 - Graph Theory / Java

• 문제 링크

2178번: 미로 탐색

 

• 풀이 과정

우선 미로의 경로를 나타낼 maze 배열과 배열의 크기로 지정될 n, m 변수,

그리고 각 좌표당 방문 여부를 체크할 visited 배열과 4방향 좌표 이동에 필요한 dx, dy 배열을 지정한다.

첫 시작 인덱스는 0, 0 이며 visited 배열에 해당 위치를 체크하고 bfs 함수에 인자로 전달해 탐색을 시작한다.

 

너비 우선 탐색 (BFS)을 활용하여 경로를 탐색할 것이므로 기본적으로 큐 (Queue) 를 활용한다.

현재 x, y 좌표값을 저장할 Loc 객체를 생성 및 제네릭으로 지정하여 연결 리스트 (LinkedList) 에 삽입한다.

 

큐에 원소가 비어있을 때까지 반복하며 큐에서 원소를 poll 하여 now 변수에 저장한다.

그 다음 for 문으로 nextX, nextY 변수에 현재 위치에서 이동하려는 4 방향을 지정하여 각각의 해당 방향으로

이동 가능 여부를 아래의 if 문에서 체크한다.

 

첫번째 if 문에서는 방문하려하는 좌표가 미로의 범위를 넘어간다면 다음 방향으로 넘어가고

두번째 if 문에서는 방문하려하는 좌표가 이미 방문했거나 이동할 수 없는 칸인 0 이라면 다음 방향으로 넘어간다.

 

이러한 조건을 통과하여 이동 가능한 다음 방향이 주어졌을 때 이동할 좌표를 큐에 삽입하고

이동할 좌표의 인덱스값을 현재 좌표의 인덱스 값 보다 1 증가한 값으로 변경해준다.

끝으로 다음 좌표 역시 방문 체크를 해주며 다시 while 문이 돌아 이동한 좌표에서 다시 탐색을 시작한다.

 

이렇게 큐에 저장된 이동가능한 경로로 너비 우선 탐색 순서로 뻗어나가며,

결국 최종 종착지인 maze[n - 1][m - 1] 에 먼저 도착하는 경로가 visited 에 체크하여

결과적으로 더 이상 큐에 값을 저장할 수 없을 것이고 while 문 또한 종료되어 이동해야 할 최소 칸이 구해지게 된다.

 

• 풀이 코드

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 {

	static int n;
	static int m;
	static int[][] maze;
	static boolean[][] visit;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		maze = new int[n][m];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) 
				maze[i][j] = s.charAt(j) - '0';
		}

		visit = new boolean[n][m];
		visit[0][0] = true;

		bfs(0, 0);

		bw.write(maze[n - 1][m - 1] + "\n");
		bw.flush();
	}

	private static void bfs(int y, int x) {
		Queue<Loc> q = new LinkedList<>();
		q.offer(new Loc(y, x));

		while (!q.isEmpty()) {
			Loc now = q.poll();
			for (int i = 0; i < 4; i++) {
				int nextY = now.y + dy[i];
				int nextX = now.x + dx[i];

				if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= m)
					continue;
				if (visit[nextY][nextX] || maze[nextY][nextX] == 0)
					continue;

				q.offer(new Loc(nextY, nextX));
				maze[nextY][nextX] = maze[now.y][now.x] + 1;
				visit[nextY][nextX] = true;
			}
		}
	}

	private static class Loc {
		int y;
		int x;

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

}