Q. 2178 자바 : 미로 탐색

Q. 2178 자바 : 미로 탐색

 

문제 : boj.kr/2178

실버 1 난이도의 문제이다.

 

격자형 그래프의 크기 N, M과 그래프가 주어졌을 때

1,1부터 N,M까지 갈 수 있는 최소 이동 횟수를 출력하는 문제이다.

주의해야 할 점은 시작점인 1, 1과 도착점인 N, M도 이동 횟수에 포함된다는 점 이다.

 

최악의 경우는 아래와 같은 경우이며

111111111
100000000
111111111
100000000
111111111
100000000
111111111

이 경우 시간복잡도는 약 O(NM)이다.

 

이 문제의 경우 N과 M의 최대값이 100이므로 시간초과는 걱정하지 않아도 된다.

또한 도착위치로 이동할 수 없는 경우는 주어지지 않는다고 했으므로 고려하지 않아도 되고,

이동 가능한 칸과 이동이 불가능한 칸이 0과 1로 주어지므로

char형의 2차원 배열을 이용해서 풀었다.

 

문제를 푼 방식을 설명하자면,

먼저 bfs를 이용해 풀었고, bfs에 이용된 큐는 int형 배열을 받는다.

int형 배열의 요소는 y, x, 움직인 횟수 3개를 가진다.

방문 체크를 해 가면서 만약 원하는 위치에 도달한 경우 움직인 횟수를 결과값으로 출력하고 종료한다.

이렇게 풀은 이유는 큐를 이용했고, 움직인 횟수는 1씩 증가하므로

가장 먼저 원하는 위치에 도달한 경우가 최소 이동 횟수임이 보장되기 때문이다.

 

푼 뒤에 강의를 들으면서 확인해보니

강의에서는 입력된 그래프와 동일한 dist 2차원 배열을 만들고,

배열의 요소들 마다 최소 이동 횟수를 저장한 뒤 결과값으로 목표 위치의 dist 배열을 출력하는 방식으로 풀었다.

(듣다보니 dp의 메모제이션 방식과 유사하다는 생각이 들었다)

그래서 강의를 참고해서 다시 풀어봤는데, 다행히도 실행 속도는 유의미한 차이가 나지는 않았다.

---

두 방식의 풀이 모두를 작성해보자면 아래와 같다

import java.io.*;
import java.util.*;


public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M, res = 10000;
    static boolean[][] graph;
//    static boolean[][] visit;
    static int[][] dist;

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


    static void input() {

        N = scan.nextInt();
        M = scan.nextInt();
        graph = new boolean[N][M];
        dist = new int[N][M];
//        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            char[] input = scan.next().toCharArray();
            for (int j = 0; j < M; j++) {
                graph[i][j] = input[j] == '1';
            }
        }
    }

//    static void bfs() { // 내가 푼 풀이
//
//        Queue<int[]> que = new LinkedList<>();
//        visit[0][0] = true;
//        que.add(new int[]{0, 0, 1}); // y, x, cnt
//
//        while (!que.isEmpty()) {
//
//            int[] cur = que.poll();
//            if (cur[0] == (N - 1) && cur[1] == (M - 1)) {
//                res = cur[2];
//                que.clear();
//                return;
//            }
//            for (int i = 0; i < 4; i++) {
//                int ny = cur[0] + dy[i];
//                int nx = cur[1] + dx[i];
//                if (ny < 0 || nx < 0 || ny == N || nx == M) continue;
//                if (!graph[ny][nx]) continue;
//                if (visit[ny][nx]) continue;
//                que.add(new int[] {ny, nx, cur[2] + 1});
//                visit[ny][nx] = true;
//            }
//        }
//    }

    static void bfs(int y, int x) {

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) dist[i][j] = -1;
        }

        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{y, x});
        dist[y][x] = 1;

        while (!que.isEmpty()) {

            int[] cur = que.poll();
            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                if (ny < 0 || nx < 0 || ny == N || nx == M) continue;
                if (!graph[ny][nx]) continue;
                if (dist[ny][nx] != -1) continue;
                que.add(new int[] {ny, nx});
                dist[ny][nx] = dist[cur[0]][cur[1]] + 1;
            }
        }
    }



    static void pro() {

//        bfs();
//        System.out.println(res);
        bfs(0, 0);
        System.out.println(dist[N - 1][M - 1]);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        // BufferedReader의 빠른 속도,
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}