[백준] 2178. 미로 탐색 (실버1, Java)

문제

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입출력 예

 

 

풀이

DFS, BFS 공부했지만 정말 감이 안왔다...

그래서 다시! 블로그 보면서 풀이 방법을 읽으면서 코드를 짜봤다. 처음에는 깊이 우선 탐색인줄 알았으나 너비였다...!

 

 

miro에는 입력값을 저장하고 check에는 방문했으면 true 값을 저장한다.

 

 

배열에 주어진 입력값을 저장하고 find 함수를 호출한다. find 함수에서 너비 우선 탁샘 알고리즘을 구현했다.

미로에서 길을 찾는 것이기 때문에 상하좌우 모든 방향을 살펴보고 갈 수 있는지 확인해야 한다.

이를 위해 필요한 1차원 배열 변수이다.

큐에는 이동 가능하지만 처음 방문한 곳을 저장한다.

 

 

 

배열 인덱스 번호를 저장할 Node 클래스를 만들었다.

 

 

 

 

 

 

 

그 다음 while 문에서 큐의 값이 없을 때까지 반복한다.

반복문에서는 처음 방문한 곳에서 상하좌우 모두 확인하면서 다음 이동할 장소를 탐색한다.

 

[ 조건 ] 

조건1. 현재 x, y값에서 상하좌우 값이 인덱스가 넘어가는지

조건2. 값이 0이거나 방문 기록이 있는지

 

위의 조건 1,2에 해당하지 않을 경우에만 이동할 수 있는 칸이라고 판단하며 큐에 해당 값을 저장한다. 또한, check 배열에 방문했다는 의미로 true값을 저장한다. miro 배열에는 여태까지 이동한 값에 1을 더해 이동한 칸의 수를 저장한다.

 

 

최종 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[][] miro;
    static boolean[][] check;

    private static void find() {
        // 상하좌우 x, y 좌표 이동
        // 앞으로, 위위로, 뒤로, 아래로
        int[] moveX = { 0, -1, 0, 1 };
        int[] moveY = { 1, 0, -1, 0 };
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0));

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            for (int i = 0; i < 4; i++) {
                int x = node.x + moveX[i];
                int y = node.y + moveY[i];
                // 인덱스 범위 벗어나면 작업 X
                if (x < 0 || y < 0 || x > miro.length - 1 || y > miro[0].length - 1) {
                    continue;
                }
                // 값이 0 이거나 방문 기록이 있으면 작업 X
                if (miro[x][y] == 0 || check[x][y]) {
                    continue;
                }

                // 인덱스 범위 안에서 값이 1이며 방문 기록이 없는 경우
                queue.offer(new Node(x, y));
                check[x][y] = true;
                miro[x][y] = miro[node.x][node.y] + 1;
            }
        }

        System.out.println(miro[miro.length - 1][miro[0].length - 1]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        miro = new int[n][m];
        check = new boolean[n][m];
        check[0][0] = true;

        for (int i = 0; i < n; i++) {
            String str = sc.next();
            char[] strArr = str.toCharArray();
            for (int j = 0; j < m; j++) {
                miro[i][j] = Integer.parseInt(strArr[j] + "");
            }
        }

        find();
    }

    static class Node {
        int x;
        int y;

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

 

 

 

백준 문제

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