[백준] 2178 미로탐색 (JAVA)

문제 링크:

2178번: 미로 탐색

 

문제:

 

입력:

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

 

출력:

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

 

 

문제 해결 방법:

미로 탐색은 대표적으로 BFS와 DFS 알고리즘을 사용한다. DFS방식은 시간초과가 발생하기 때문에 BFS방식으로 해결하면 된다. 작성자는 DFS 방식도 첨부할 것이다.

 

BFS(너비우선 탐색)으로 예제입력 1을 통해 15가 어떻게 나오는지 먼저 알아보자.

위 그림과 같이 너비우선 탐색을 진행한다. 즉, 현재 지점에서 갈 수 있는 모든 방향을 검사하여 조건에 맞는 칸(길이 존재하고 아직 방문하지 않은 칸)이라면, 그 칸을 큐에 넣고 다음 탐색 대상으로 삼는다.
이 과정을 큐가 빌 때까지 반복함으로써, 우리는 시작 지점부터 목표 지점까지의 최단 경로를 계산할 수 있게 되는 것이다.

 

 

  해결 방법 요약

1. 미로를 2차원 배열로 입력받는다.
   각 칸은 숫자 1 또는 0으로 구성되어 있으며, 1은 이동 가능한 길, 0은 벽을 의미한다.
2. 방문 여부를 체크할 배열 visited[][]를 선언한다.
   이 배열은 각 칸을 한 번만 방문하도록 도와준다.
   이미 방문한 칸을 다시 탐색하지 않기 위해 사용한다.
3. BFS 탐색을 위한 큐(Queue)를 생성한다.
   탐색은 시작 지점 (1, 1)에서 시작하며, 이 위치를 큐에 넣고 방문 처리를 한다.
4. 현재 위치에서 상하좌우 네 방향으로 한 칸씩 이동할 수 있는지 검사한다.
   각 방향으로 이동 가능한지 판단할 때는 다음 조건을 모두 만족해야 한다:
   • 이동하려는 좌표가 미로 범위 안에 있는지
   • 해당 칸이 길(1) 인지
   • 아직 방문하지 않은 곳인지
5. 이동이 가능하다면, 그 칸을 큐에 넣고 방문 처리한다.
   그리고 현재 위치까지의 이동 횟수에 +1을 더해, 해당 칸에 최단 거리를 누적하여 저장한다.
   예를 들어, (x, y)에서 (nextX, nextY)로 이동할 경우:
   miro[nextX][nextY] = miro[x][y] + 1;
   
   
6. 이 과정을 큐가 빌 때까지 반복한다.
   BFS는 너비 우선 탐색이기 때문에, 먼저 도달한 경로가 곧 최단 경로가 된다.
7. 탐색이 종료되면, 도착 지점의 값에는 시작 지점부터 그 위치까지의 최단 이동 횟수가 저장되어 있다.
   이 값을 출력하면 정답이 된다.

 

이를 코드로 그대로 구현하면 다음과 같다.

    public static void bfs(int startX, int startY) {
        Queue<int[]> q = new LinkedList<>();
        visited[startX][startY] = true;
        q.add(new int[]{startX, startY});

        while (!q.isEmpty()) {
            int[] pos = q.poll();
            int x = pos[0];
            int y = pos[1];

            // 아래쪽 이동
            if (x + 1 < miro.length && miro[x + 1][y] == 1 && !visited[x + 1][y]) {
                visited[x + 1][y] = true;
                miro[x + 1][y] = miro[x][y] + 1;
                q.add(new int[]{x + 1, y});
            }

            // 위쪽 이동
            if (x - 1 >= 1 && miro[x - 1][y] == 1 && !visited[x - 1][y]) {
                visited[x - 1][y] = true;
                miro[x - 1][y] = miro[x][y] + 1;
                q.add(new int[]{x - 1, y});
            }

            // 오른쪽 이동
            if (y + 1 < miro[0].length && miro[x][y + 1] == 1 && !visited[x][y + 1]) {
                visited[x][y + 1] = true;
                miro[x][y + 1] = miro[x][y] + 1;
                q.add(new int[]{x, y + 1});
            }

            // 왼쪽 이동
            if (y - 1 >= 1 && miro[x][y - 1] == 1 && !visited[x][y - 1]) {
                visited[x][y - 1] = true;
                miro[x][y - 1] = miro[x][y] + 1;
                q.add(new int[]{x, y - 1});
            }
        }
    }

 

 

DFS방식을 추가하고 메인함수를 추가한 최종 코드는 다음과 같아진다.

 

정답 코드:

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

public class Main {

    static int[][] miro;
    static boolean[][] visited;
    static int weigh, height;
    static int minVal = Integer.MAX_VALUE;


    //bfs방식
    public static void bfs(int startX, int startY) {
        Queue<int[]> q = new LinkedList<>();
        visited[startX][startY] = true;
        q.add(new int[]{startX, startY});

        while (!q.isEmpty()) {
            int[] pos = q.poll();
            int x = pos[0];
            int y = pos[1];

            // 아래쪽 이동
            if (x + 1 < miro.length && miro[x + 1][y] == 1 && !visited[x + 1][y]) {
                visited[x + 1][y] = true;
                miro[x + 1][y] = miro[x][y] + 1;
                q.add(new int[]{x + 1, y});
            }

            // 위쪽 이동
            if (x - 1 >= 1 && miro[x - 1][y] == 1 && !visited[x - 1][y]) {
                visited[x - 1][y] = true;
                miro[x - 1][y] = miro[x][y] + 1;
                q.add(new int[]{x - 1, y});
            }

            // 오른쪽 이동
            if (y + 1 < miro[0].length && miro[x][y + 1] == 1 && !visited[x][y + 1]) {
                visited[x][y + 1] = true;
                miro[x][y + 1] = miro[x][y] + 1;
                q.add(new int[]{x, y + 1});
            }

            // 왼쪽 이동
            if (y - 1 >= 1 && miro[x][y - 1] == 1 && !visited[x][y - 1]) {
                visited[x][y - 1] = true;
                miro[x][y - 1] = miro[x][y] + 1;
                q.add(new int[]{x, y - 1});
            }
        }
    }

    //dfs방식
    public static void dfs(int startX, int startY, int count) {
        visited[startX][startY] = true;

        if (startX == weigh && startY == height) {
            minVal = Math.min(minVal, count);
            visited[startX][startY] = false;  // 복구
            return;
        }

        if (count > minVal) {
            visited[startX][startY] = false;  // 복구
            return;
        }

        // 상
        if (startX > 0 && !visited[startX - 1][startY] && miro[startX - 1][startY] == 1) {
            dfs(startX - 1, startY, count + 1);
        }

        // 하
        if (startX + 1 < miro.length && !visited[startX + 1][startY] && miro[startX + 1][startY] == 1) {
            dfs(startX + 1, startY, count + 1);
        }

        // 좌
        if (startY > 0 && !visited[startX][startY - 1] && miro[startX][startY - 1] == 1) {
            dfs(startX, startY - 1, count + 1);
        }

        // 우
        if (startY + 1 < miro[0].length && !visited[startX][startY + 1] && miro[startX][startY + 1] == 1) {
            dfs(startX, startY + 1, count + 1);
        }

        visited[startX][startY] = false;  // 복구
    }


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        weigh = Integer.parseInt(input[0]);  // 행 수
        height = Integer.parseInt(input[1]); // 열 수

        miro = new int[weigh + 1][height + 1];
        visited = new boolean[weigh + 1][height + 1];

        //입력값 행렬 저장.
        for (int i = 1; i <= weigh; i++) {
            String line = br.readLine();
            for (int j = 1; j <= height; j++) {
                miro[i][j] = line.charAt(j - 1) - '0';
            }
        }

        /**
         * bfs탐색
         */
        bfs(1, 1);
        System.out.println(miro[weigh][height]);

        /**
         * dfs탐색
         */
//        dfs(1,1,1);
//        System.out.println(minVal);
    }
}

 

 

BFS 방식은정답 DFS 방식은 시간초과가 발생한 것을 확인할 수 있다.

 

 

마무리:

작성자는  상 하 좌 우 방향에 대해 더 직관적인 코드를 작성하기 위해 4가지 if문을 통해 사용하였다.

 

이를 배열로 사용하여 중복 코드를 제거할 수 있지만,

위와 같이 직관적으로 작성하여 공부를 진행하고

익숙해 진 다음에  배열을 사용하는 것을 추천한다.