[백준] 2178번 미로 탐색

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

2178번: 미로 탐색

---

접근 방식

 

• 미로를 최소의 칸을 지나서 이동해야한다. -> 경로를 탐색하기 위해 dfs/bfs를 사용해야하는데 조건 중 '최소'가 있다. dfs를 사용할 경우 모든 경로를 다 탐색하기 때문에 시간 초과가 날 수 있을 것이라 생각하고 bfs를 사용하기로 했다.
• bfs 이기 때문에 queue를 사용했다. 
• 미로의 상하좌우를 탐색하기 위한 x,y 배열을 생성한 후, 각 배열을 반복하여 더해줬을 때 다음 위치가 유효한지 확인하여 탐색할 수 있도록 했다. 

 

+ ) 주석처리된 부분으로, 반복할 때마다 어떻게 업데이트 되어지는지 확인할 수 있다. 

package yejin.song;

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 BOJ_미로탐색 {
    static int[][] map;
    static int n;
    static int m;
    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0 }; //x방향배열-상하
    static int[] dy = { 0, 0, -1, 1 }; //y방향배열-좌우

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

        // 미로 배열 초기화
        map = new int[n][m];

        // map에 저장
        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';
            }
        }

        // 방문 배열 초기화
        visited = new boolean[n][m];

        // 시작 노드 방문표시
        visited[0][0] = true;

        // 함수 호출하여 최단 거리 계산하기
        bfs(0, 0);
        System.out.println(map[n-1][m-1]);
    }

    public static void bfs(int x, int y) {

        // 좌표(0,0)를 담기위해 int[] 를 담는 큐 생성
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x,y});

        while(!q.isEmpty()) {
            int now[] = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            // 모든 가능한 방향(상,하,좌,우) 반복
            for(int i=0; i<4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                // 다음 위치 유효한지 확인 : 방문한 적 없고 벽이 아니어야 함, 값이 1 이어야함.
                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
                    continue;
                if (visited[nextX][nextY] || map[nextX][nextY] == 0)
                    continue;

                // 다음 위치를 큐에 추가
                q.add(new int[] {nextX, nextY});
                // 거리 정보 업데이트
                map[nextX][nextY] = map[nowX][nowY] + 1;

//                System.out.println("q:");
//                printQueue(q);
//                System.out.println("i:" + i);
//                System.out.println("map:");
//                printMap(map);
                // 방문한 위치로 추가
                visited[nextX][nextY] = true;
            }
        }
    }

//    // 큐의 내용을 출력하는 함수
//    public static void printQueue(Queue<int[]> queue) {
//        System.out.print("q: ");
//        for (int[] element : queue) {
//            System.out.print(Arrays.toString(element) + " ");
//        }
//        System.out.println();
//    }
//
//    // 배열의 내용을 출력하는 함수
//    public static void printMap(int[][] arr) {
//        for (int[] row : arr) {
//            System.out.println(Arrays.toString(row));
//        }
//    }

}

 

1. 미로 입력에 공백이 들어가지 않으므로, string으로 받고, 한 글자씩 map에 삽입한다.
2. 방문 체크를 위한 visited 배열을 준비하고, 첫 시작인 0,0 인덱스를 true로 설정한다.
3. 시작 인덱스 0,0을 넘기며 bfs 함수를 시작한다.
  3-1. 이동 가능한 칸들의 인덱스를 저장할 Queue를 선언한다. (x,y)쌍의 int형 배열을 저장.
  3-2. 넘겨받은 x,y를 int형 배열로 만들어 큐에 삽입.
4. 큐가 비어있지 않다면 반복
  4-1. 큐에서 원소 하나를 꺼내 각각 인덱스를 nowX, nowY에 저장한다.
  4-2. (nowX, nowY)를 기준으로 상하좌우를 확인해서 이동 가능한 인덱스가 있다면 그 인덱스를 큐에 저장한다.
  4-3. 그 인덱스의 값을 현재 인덱스(nowX, nowY)값보다 1 큰 값으로 설정한다. (-> 가장 최단거리인지 계속 더해줌)
  4-4. 그 인덱스의 방문체크를 한다.

 

 

+++ 예제 입력 1에 대한 출력 결과

"/Applications/IntelliJ IDEA.app/Contents/jbr/Contents/Home/bin/java" -javaagent:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=50063:/Applications/IntelliJ IDEA.app/Contents/bin -Dfile.encoding=UTF-8 -classpath /Users/song-yejin/IdeaProjects/algorithm-study/out/production/algorithm-study yejin.song.BOJ_미로탐색
4 6
101111
101010
101011
111011
q:
q: [1, 0] 
i:1
map:
[1, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
q:
q: [2, 0] 
i:1
map:
[1, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
q:
q: [3, 0] 
i:1
map:
[1, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[4, 1, 1, 0, 1, 1]
q:
q: [3, 1] 
i:3
map:
[1, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[4, 5, 1, 0, 1, 1]
q:
q: [3, 2] 
i:3
map:
[1, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 1, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [2, 2] 
i:0
map:
[1, 0, 1, 1, 1, 1]
[2, 0, 1, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [1, 2] 
i:0
map:
[1, 0, 1, 1, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [0, 2] 
i:0
map:
[1, 0, 9, 1, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [0, 3] 
i:3
map:
[1, 0, 9, 10, 1, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [0, 4] 
i:3
map:
[1, 0, 9, 10, 11, 1]
[2, 0, 8, 0, 1, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [1, 4] 
i:1
map:
[1, 0, 9, 10, 11, 1]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [1, 4] [0, 5] 
i:3
map:
[1, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 1, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [0, 5] [2, 4] 
i:1
map:
[1, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 1]
[4, 5, 6, 0, 1, 1]
q:
q: [3, 4] 
i:1
map:
[1, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 1]
[4, 5, 6, 0, 14, 1]
q:
q: [3, 4] [2, 5] 
i:3
map:
[1, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 1]
q:
q: [2, 5] [3, 5] 
i:3
map:
[1, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]
15

종료 코드 0(으)로 완료된 프로세스