Java 백준 문제풀이 (54) 미로 탐색

기본 중의 기본인 미로 찾기 문제다.

한 번 풀어보고나면 딱히 어려울 건 없지만 2차원 배열을 다루는 만큼 처음부터 생각을 잘 해놓고 시작해야 한다.

 

 

// 2차원 배열 길 찾기 문제 특) 상하좌우 이동용 배열 필요함
// 최단거리 문제 특) bfs가 좋다
// 메모리 192MB => 최대값인 int[100][100]으로 2개 만들고 visited[100][100] 만들어도 남아돈다.

처음 작성한 주석은 이렇게 세 줄이다.

2차원 배열 길찾기 문제라서 일단 상하좌우 이동용 배열이 필요하다.

1. {1,0,-1,0} . {0,1,0,-1} 이렇게 두 개 있으면 된다.

 

2. 최단거리 문제는 bfs가 dfs보다 유리하다.

왜일까요?

dfs는 조건에 맞지 않으면 처음부터 다시 탐색하는 걸 반복한다.

bfs는 같은 depth에서 탐색할 수 있는 모든 경우의 수를 구해놓고 하나씩 탐색한다.

당연히 bfs가 더 빠를 수 밖에 없다.

헷갈리면 예제 하나 캡쳐해서 위에 그려보자.

 

느린 건 둘째치더라도, DFS 같은 경우 한 번 가는 길이 뚫려있으면 끝까지 탐색한다는 특성 때문에 최단거리 구할 때는 조건도 더 신경써줘야해서 귀찮다.

(더 멀리 가야하는 루트로 종점을 먼저 방문해버리면?)

BFS는 알고리즘 특성상 절대로 느린 경로로 출발한 쪽이 먼저 도착할 수 없다.

 

3. 40000byte + 40000byte + 10000byte

공간 복잡도는 전혀 신경 쓸 필요 없는 넉넉한 용량을 제공해주고 있다.

메모이제이션으로 답을 구하자.

문제에서 제시해주는 크기의 배열을 하나 더 만들고, 이동한 카운트를 해당 배열의 같은 인덱스에 대응해서 카운트해주자는 의미다.

bfs에서 어떤 노드에 방문했다면 항상 최단거리이기 때문에 이전 방문 노드 값 +1만 해주면 된다.

왜 항상 최단거리일까요?

늘 이전 노드랑 1칸 밖에 차이나지 않으니까요.

 

 

조건에 맞춰서 야매 수도코드를 작성해봤다.

 

import java.util.*;
import java.io.*;
 
public class Main {
    // 상하좌우 이동용 배열 생성
    private static final int[] dr1 = {1,0,-1,0};
    private static final int[] dr2 = {0,1,0,-1};
    private static final int FOUR_WAY = 4;
    // 방문 기록용 배열 생성
    private static boolean[][] visited;
    // 지도 기록용 2차원 배열 생성
    private static int[][] map;
    // N, M
    private static int N;
    private static int M;
    // 정답
    private static int[][] answer;
 
    public static void main(String[] args) throws Exception {
        // 4차원 배열 찾기 문제 특) 상하좌우 이동용 배열 필요함
        // 최단거리 문제 특) bfs가 좋다
        // 메모리 192MB => 최대값인 int[100][100]으로 2개 만들고 visited[100][100] 만들어도 남아돈다.
 
        // 정수 N, M 입력 받기
 
        // 지도 초기화
 
        // 이중 반복문
        // N번만큼 반복하며 M개의 수 배열에 입력
 
        // visited 초기화
 
        // bfs 시작
 
        // 정답 출력
    }
 
    private static void bfs(int[] node) {
        //큐 생성
 
        //큐에 노드 삽입
 
        //While (널이 아닐 때까지)
            // 큐에서 가장 앞의 인자 빼기
            // 반복문 (4방향 돌면서 체크)
 
                // 조건문 (ArrayIndexOutOfBoundsException 일어나지 않는다면 && 1인가요)
                // 만약 방문한 적 없다면
                // x랑 y를 q에 넣어주세요.
                // 방문 체크해주세요.
            }
        }
    }
}

 

원래는 정적 변수를 잘 사용하지 않았었는데

쓸데없이 제약 걸고해서 시간만 더 걸리는 느낌이라 그냥 어지간한 건 다 정적 변수로 선언하기로 했다.

 

그럭저럭 괜찮게 작성한 것처럼 보일 수도 있지만 이렇게 풀다가 중간에 생각 한 번 꼬이면 망한다. (내 얘기)

 

2차원 배열 다루는 문제는 처음 시작할 때 아는 문제 유형이라고 대충 잡아놓고 시작했다가 실수하면 어디서 틀린건지 찾아내기가 너무 괴로워진다.

나는 요즘 IDE를 사용하지 않고 백준으로만 문제 푸는 것을 시도 중인데, 오늘은 어디서부터 망친 건지 감도 안와서 결국 IDE를 켰다.

고수가 아니면 처음부터 잘 생각하고 시작하자..

 

빼먹은 게 너무 많다.

1. answer에 대한 값은 어디서 더할 것인지

2. visited는 정확히 어디서 체크할 것인지

3. 2중 반복문은 헷갈리니까 [x][y]도 주석에서 미리 다 적어주는 게 실수를 막는 길이다.

4. while문 내부도 풀다가 생각하면 헷갈리니까 처음부터 정해놓자.

 

다 알려드렸으니까 님들도 풀어보삼

정답은 아래에

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    // 상하좌우 이동용 배열 생성
    private static final int[] dr1 = {1,0,-1,0};
    private static final int[] dr2 = {0,1,0,-1};
    private static final int FOUR_WAY = 4;
    // 방문 기록용 배열 생성
    private static boolean[][] visited;
    // 지도 기록용 2차원 배열 생성
    private static int[][] map;
    // N, M
    private static int N;
    private static int M;
    // 정답
    private static int[][] answer;
 
    public static void main(String[] args) throws Exception {
        // 4차원 배열 찾기 문제 특) 상하좌우 이동용 배열 필요함
        // 최단거리 문제 특) bfs가 좋다
        // 값이 많아봐야 10000개 -> 뭘로 해도 풀긴 할 듯
 
        // 정수 N, M 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        N = Integer.parseInt(s[0]);
        M = Integer.parseInt(s[1]);
 
        // 지도 초기화
        map = new int[N][M];
        answer = new int[N][M];
 
        // 이중 반복문
        // N번만큼 반복하며 M개의 수 배열에 입력
        for (int i=0; i<N; i++) {
            String[] strArr = br.readLine().split("");
 
            for (int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(strArr[j]);
            }
        }
 
        // visited 초기화
        visited = new boolean[N][M];
 
        // bfs 시작
        bfs(new int[]{0,0});
 
        System.out.println(answer[N-1][M-1]);
    }
 
    private static void bfs(int[] node) {
        //큐 생성
        Queue<int[]> queue = new ArrayDeque<>();
        //큐에 노드 삽입
        queue.add(node);
        visited[0][0]=true;
        answer[0][0] += 1;
 
        //While (널이 아닐 때까지)
        while (!queue.isEmpty()) {
            // 큐에서 가장 앞의 인자 빼기
            int[] next = queue.poll();
 
            // 반복문 (4방향 돌면서 체크)
            for (int i=0; i<FOUR_WAY; i++) {
                // 조건문 (ArrayIndexOutOfBoundsException 일어나지 않는다면 && 1인가요)
                int x = next[1] + dr1[i];
                int y = next[0] + dr2[i];
 
                if (x>=0 && x<map[0].length && y>=0 && y<map.length && !visited[y][x] && map[y][x]==1) {
                    queue.add(new int[]{y, x});
                    visited[y][x] = true;
                    answer[y][x] = answer[next[0]][next[1]] + 1;
                }
                // 만약 방문한 적 없다면
                // x랑 y를 q에 넣어주세요.
                // 방문 체크해주세요.
            }
        }
    }
}