백준 2178 자바 풀이

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

2178번: 미로 탐색

DFS로 풀었다가 시간초과가 나서 BFS로 변경해 풀었다.

달라진 것은 당연히 DFS는 재귀, BFS는 큐를 이용한다는 것이다.

최단 거리를 구할 땐 BFS를 쓰는게 최소값을 구하기 위해 비교하지 않아도 되고 편하다! visit 배열을 boolean에서 int 형으로 바꿔 뎁스를 표시 해줬는데, 이는 이전에 풀었던 백준 1697번 문제와 같은 방식이다. 그땐 그 풀이가 잘 이해되지 않았는데 이번 문제를 통해 BFS 최단거리 알고리즘을 확실히 알게 되었다.

 

코드는 DFS로 풀었던 것 까지 놔두었다. 다른 블로그들을 보면 백준에서 시간만 넉넉히 주면 틀린 풀이는 아니라고 한다.

import java.awt.*;
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 bj2178 {

    static int N, M;
//    static int min;
    static char[][] map;
    static int[][] visit; //visit 배열을 boolean 이 아닌 int 형으로 변경 -> 뎁스(최단거리) 확인
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

    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 char[N][M];
        visit = new int[N][M];
//        min = 201;

        for(int i = 0; i < N; i ++) {
            String temp = br.readLine();
            map[i] = temp.toCharArray();
        }

//        DFS(0, 0 , 0);
//
//        System.out.println(min + 1);

        BFS();

        System.out.println(visit[N - 1][M - 1]);
    }

    public static void BFS() {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(0 ,0));
        visit[0][0] = 1;

        while(!q.isEmpty()) {
            Point cur = q.poll();

            for(int i = 0; i < dx.length; i ++) {
                int nx = dx[i] + cur.x;
                int ny = dy[i] + cur.y;

                if(nx < N && nx >= 0 && ny < M && ny >= 0 && visit[nx][ny] == 0 && map[nx][ny] == '1') {
                    q.offer(new Point(nx, ny));
                    visit[nx][ny] = visit[cur.x][cur.y] + 1;
                }
            }
        }
    }

//    public static void DFS(int x, int y, int cnt) {
//
//        if(x == N - 1 && y == M - 1) {
//            if(min > cnt) min = cnt;
//            return;
//        }
//
//        visit[x][y] = true;
//
//        for(int i = 0 ; i < dx.length; i ++) {
//            int nx = dx[i] + x;
//            int ny = dy[i] + y;
//
//            if(nx < N && nx >= 0 && ny < M && ny >= 0) {
//                if(!visit[nx][ny] && map[nx][ny] == '1') {
//                    DFS(nx, ny, cnt + 1);
//                    visit[nx][ny] = false;
//                }
//            }
//        }
//    }
}