[백준] 2178 미로 탐색 - Java

문제 - 미로 탐색

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

 

 

입력

 

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

 

 

출력

 

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

 

 

예제 입력

4 6
101111
101010
101011
111011

 

예제 출력

15

---

접근 방법

 

이 문제는 bfs로 최단 거리의 수를 구하는 문제이다

dfs로 풀면  시간 초과가 난다(작성자는 dfs로 무작정 풀다가 낙심했다..)

그 이유는 dfs로 풀시 끝까지 탐색하고 다시 돌아오고 그런식으로 반복하다 보니 시간이 오래 걸린다

그리고 방문했던 곳을 다시 방문 안해도 되는데 계속 왔다 갔다 해야하는 점이 효율성이 떨어진다

---

코드 작성

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

public class Main {
    static int N;
    static int M;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] miro;
    static boolean[][] visited;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

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

            for (int i = 0; i < N; i++) {
                miro[i] = Arrays.stream(br.readLine().split(""))
                	.mapToInt(Integer::parseInt)
                	.toArray();
            }

            findMiro(0, 0);

            System.out.println(miro[N - 1][M - 1]);

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public static void findMiro(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;


        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int pollX = poll[0];
            int pollY = poll[1];

            for (int i = 0; i < 4; i++) {
                int ix = pollX + dx[i];
                int iy = pollY + dy[i];

                if (ix >= 0 && ix < N && iy >= 0 && iy < M) {
                    if (!visited[ix][iy] && miro[ix][iy] != 0) {
                        miro[ix][iy] += miro[pollX][pollY];
                        visited[ix][iy] = true;
                        queue.add(new int[] {ix, iy});
                    }
                }
            }
        }
    }
}

---

풀고 느낀점

 

• 이 문제는 좌측 상단에서 우측 하단 까지 탐색하여 거리를 측정하는 문제이다
• 기본적인 BFS 문제이다 
• 시작 점과의 거리를 계속 기록하면서 방문 하면 쉽게 풀린다
• BFS와 DFS 의 차이점을 알고 적절하게 사용하면 좋을 것 같다