2178. 미로 탐색

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

2178번: 미로 탐색

 

미로의 처음에서 끝까지 도달할수 있는 최소 칸 수를 구하는 문제.

옛날부터 잘은 몰라도 미로문제는 bfs로 푼다고 어디서 주워는 들어서 bfs로 푸는 것은 처음 부터 알았다.

 

미로가 만약 이렇게 주어지면

일단 (0,0)에서 시작하니 큐에 (0,0)을 넣는다

큐 : (0,0)

 

(0,0)에서 이동할수 있는 곳은 (1,0) 뿐이다.

큐 : (1,0)     // (0,0)은 제거됨

 

(1,0)에서 이동할수 있는 곳은 (2,0)

큐 : (2,0)

 

... 이렇게 쭉 가다가 (0,4)에 오면 

큐 : (0,4)

에서 갈 수 있는 곳이 두곳 (0,5), (1,4)이다.

 

큐: (0,5), (1,4)

그런데 각 칸으로 갈때 그 칸까지 가는데 몇칸이 걸렸는지 기록해야하는데 

이렇게 한 칸에서 갈 수있는곳이 두칸 이상일때 칸 수가 2이상 더해지지 않도록 해야한다.

 

 

이전 문제 비슷하게 잘풀다가 문제를 맞닥트렸다.

나는 큐에 좌표 하나를 넣을때마다 1을 더하고 좌표에서 갈곳이 없으면 1을 빼고.. 이런식으로하면 최종적으로 

최소 이동 칸 수를 구할수 있을줄 알았는데 잘 안됐다.

 

고민하다가 배열을 하나더 만들어서 이동할때마다 그 칸 까지 도달하는 칸수를 기록해보기로 했다.

이렇게 기록하면 마지막 도착칸의 수에 1을 더하면 답이 된다.

 

코드

import java.util.*;

public class Main {
    static int[][] arr; // 미로 저장
    static int[][] visit; // 방문 여부
    static int[][] arr_n;
    static int n, m;
    static int num = 0;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n][m];
        visit = new int[n][m];
        arr_n = new int[n][m];

        // 미로 저장
        for(int i = 0; i < n; i++) {
            String temp = sc.next();

            for(int j = 0; j < m; j++) {
                arr[i][j] = temp.charAt(j)-'0'; // string to int
            }
        }

        bfs();

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                System.out.format("%d ", arr_n[i][j]);
            }
            System.out.println();
        }

        System.out.println(arr_n[n-1][m-1] + 1);


    }

    static void bfs() { // a:n, b:m
        int a = 0, b = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        visit[a][b] = 1;
        q.add(0); q.add(0);

        int trigger_n = 1; // 큐에 두개 이상 들어갔을때 다음에 모두 큐에서 빼야함
        while(!q.isEmpty()) {
            int trigger = 0;
            num++;
            for(int i = 0; i < trigger_n; i++) {

                a = q.remove();
                b = q.remove();


                if (b + 1 < m && arr[a][b + 1] == 1 && visit[a][b + 1] == 0) { // 우
                    q.add(a);
                    q.add(b + 1);
                    visit[a][b + 1] = 1;
                    trigger++; // 큐에 좌표 하나 넣을때마다 trigger값도 하나 증가
                    arr_n[a][b + 1] = num;
                    if (a == n - 1 && b + 1 == m - 1) break;
                }
                if (b - 1 >= 0 && arr[a][b - 1] == 1 && visit[a][b - 1] == 0) { // 좌
                    q.add(a);
                    q.add(b - 1);
                    visit[a][b - 1] = 1;
                    trigger++;
                    arr_n[a][b - 1] = num;
                    if (a == n - 1 && b - 1 == m - 1) break;
                }
                if (a - 1 >= 0 && arr[a - 1][b] == 1 && visit[a - 1][b] == 0) { // 상
                    q.add(a - 1);
                    q.add(b);
                    visit[a - 1][b] = 1;
                    trigger++;
                    arr_n[a - 1][b] = num;
                    if (a - 1 == n - 1 && b == m - 1) break;
                }
                if (a + 1 < n && arr[a + 1][b] == 1 && visit[a + 1][b] == 0) { // 하
                    q.add(a + 1);
                    q.add(b);
                    visit[a + 1][b] = 1;
                    trigger++;
                    arr_n[a + 1][b] = num;
                    if (a + 1 == n - 1 && b == m - 1) break;
                }

            }
            if(trigger == 0) trigger++; // 큐에 하나도 안넣었어도 for문 동작위해 trigger를 1로만들어줌
            trigger_n = trigger;

        }
    }
}

 

 

---

solution

 

내가 푼 것과 알고리즘 자체는 거의 같지만 방문단계를 갱신하는 방법이나, Pair을 이용한것, 배열을 이용한 방향탐색

같이 .. 그냥 훨씬 깔끔하다.

 

static void bfs(int r, int c) {
        Queue<Pair> q = new LinkedList<Pair>();

        int index = 1; // 첫 단계 부터 시작
        q.add(new Pair(r, c));
        d[r][c] = index; // 단계값 마킹

        while(!q.isEmpty()) {
            Pair _p = q.remove();
            // 방금 제거한 위치에서의 단계값이 현재값보다 높으면..
            // 현재 단계의 정점은 모두 없어졌다고 볼 수 있기 때문에 단계를 높인다.
            if(d[_p.r][_p.c] > index) index++;

            // 4방향을 모두 탐색한다
            for(int k = 0; k < 4; k++) {
                int nr = _p.r + dr[k];
                int nc = _p.c + dc[k];
                if(0 <= nc && nc < w && 0 <= nr && nr < h) {
                    // 갈 수 있는 정점이고, 마킹이 안된 상태라면.
                    if(a[nr][nc] == 1 && d[nr][nc] == 0) {
                        q.add(new Pair(nr, nc));
                        d[nr][nc] = index + 1; // 한 단계 높여서 마킹.
                    }
                }
            }
        }
    }

Pair와 방향 탐색을 배열을 이용해서 내 코드보다 훨씬 짧고 깔끔하다.

그리고 큐에서 Pair를 뺄때 그 위치에서의 단계값이 현재값보다 높으면 단계를 높임으로서

방문단계를 갱신하고 있다.

 

 

 

그리고 애초에 나는 방문단계를 위한 배열을 따로, 방문 여부를위한 배열을 따로 만들었는데

생각해보면 그냥 하나만 필요하다.