[백준/S1/BFS/자바] 2178 미로 탐색

💡 문제

 

N × M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

 

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.

이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때

지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다.

칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

⌨ 입력

 

첫째 줄 N, M

이후 N개의 줄 : M개의 정수로 미로가 주어진다. ( 2 <= N , M <= 100 )

 

💻 출력 / 제한

 

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. / 시간 제한 : 1초 / 메모리 : 192MB

 

---

 

풀이 방법

 

최단 거리를 구하는 BFS 문제 입니다.

 

DFS 와 BFS 차이를 알아 보겠습니다.

 

📚 DFS 란?

깊이 우선 탐색으로 가능한 깊이 있는 노드를 우선으로 방문 하고,
더 이상 갈 수 없을 때 뒤로 돌아와서 다른 경로를 탐색 하는 방식입니다.

 

DFS 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class Main {
    static int[][] arr;
    static boolean[][] visited;
    static Queue<Integer> q;
    static int min = Integer.MAX_VALUE;

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

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

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

        q = new LinkedList<>();

        bfs(0,0,1);

        System.out.println(min);
    }
    static void bfs(int row, int col, int depth){

        if(row == arr.length - 1 && col == arr[0].length - 1){
            min = Math.min(depth,min);
        }

        visited[row][col] = true;

        int newDepth = depth + 1;

        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};

        for(int i = 0; i < 4; i++){
            int x = row + dx[i];
            int y = col + dy[i];

            boolean error = x < 0 || y < 0 || x > (arr.length - 1) || y > (arr[0].length - 1);

            if(!error && !visited[x][y] && arr[x][y] == 1){
                bfs(x,y, newDepth);
            }
        }

        visited[row][col] = false;
    }
}

 

DFS 시간 복잡도 : 2의  ( 노드 의 수 ) 승 입니다.

DFS 풀이는 시간 초과 입니다. ( N, M = 100 /  최대 2의 200승 )

 

📚 BFS 란?

너비 우선 탐색으로 시작 노드에서 출발하여 인접한 노드를 먼저 탐색 한후,
그 다음 단계의 노드들을 탐색 하는 방식 입니다.

 

BFS 시간 복잡도 :  노드의 수 입니다.

해당 배열은 N * M 이므로  100 * 100  = 10000 입니다.

 

예시)

 

 

첫 노드 부터 탐색을 시작하며 인접한 노드가 조건에 맞다면,

큐에 넣고 값 업데이트 합니다. 전체 탐색 하며 배열을 채웁니다.

 

 

---

전체 코드

 

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class MiroQuest {
    static int[][] arr;
    static int[][] visited;

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

        arr = new int[N][];
        visited = new int[N][M];

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

        visited[0][0] = 1;
        bfs(0,0);

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

    static void bfs(int StartX, int StartY){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {StartX,StartY});

        while(!q.isEmpty()) {

            int[] pollNum = q.poll();
            int pollX = pollNum[0]; int pollY = pollNum[1];

            int[] dx = {1, 0, 0, -1};
            int[] dy = {0, 1, -1, 0};

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

                boolean error = x < 0 || y < 0 || x > (arr.length - 1) || y > (arr[0].length - 1);

                if (!error && visited[x][y] == 0 && arr[x][y] == 1) {
                    q.add(new int[] {x,y});
                    visited[x][y] = visited[pollX][pollY] + 1;
                }
            }
        }
    }
}