BOJ 2178 미로 탐색

문제 분석

- bfs로 이동하면서 각 좌표와 depth값만 신경써서 풀어주면 쉽게 풀 수 있다.

 

 

문제 풀이

1) 각 미로의 값을 입력받는다.

2) bfs를 돌린다.

3) 노드 클래스를 활용하여 각 좌표와 depth를 계산하며 최종 목표에 도달했을 경우 해당 depth에 +1하여 출력한다. (마지막 도달한 경로도 +1해야하기때문에 depth에다가 +1하여 출력한다)

 

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 {
	private static int N, M;
	private static int[][] map;
	private static boolean[][] visited;
	private static int[] dr = { -1, 1, 0, 0 };
	private static int[] dc = { 0, 0, -1, 1 };

	private static void input() 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());

		map = 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++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}

		bfs(0, 0);
	}// input()

	private static void bfs(int sx, int sy) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(sx, sy, 0));
		visited[sx][sy] = true;

		while (!q.isEmpty()) {
			Node cur = q.poll();
			int r = cur.x;
			int c = cur.y;
			int d = cur.depth;

			if ((r == N - 1) && (c == M - 1)) {
				System.out.println(d + 1);
				break;
			}

			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) {
					if ((map[nr][nc] == 1) && !visited[nr][nc]) {
						q.add(new Node(nr, nc, d + 1));
						visited[nr][nc] = true;
					}
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		input();
	}

	static class Node {
		int x, y, depth;

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

	}
}