[백준] 2178 미로탐색 java

1. 문제 설명

[문제 링크](https://www.acmicpc.net/problem/2178)

2. 접근 방식

BFS의 경우 시작 노드에서 갈 수 있는 가장 가까운 노드 계층부터 우선적으로 가기 때문에, 시작 노드에서 목적지 노드까지 가는 최단 경로로 가는 것을 보장한다. 따라서 해당 문제는 BFS로 푼다.

이전의 BFS문제와의 차이점은 해당 문제가 그래프가 아닌 2차원 배열로 입력값이 주어진다는 것이다. 하지만 다를 것은 없고, `시작 노드에서 위 아래 좌 우 붙어있는 행렬 값` == `인접 정점` 이라고 생각하면 된다. 문제는 다음과 같이 풀었다.

1. ArrayDeque를 만들어서, 시작 행렬을 집어넣는다.
2. ArrayDeque가 빌 때까지 큐안의 값을 꺼내서, 사방 탐색하고, 미방문 행렬의 경우 queue에 집어넣는다.
3. 시작 정점으로부터 깊이가 같은 계층끼리는 비용이 같다. 만약 시작 정점이 다음과 같이 정중앙에 있다고 해보자. 

   

   

   

4. 한 칸 가는데 비용이 1이 든다면, 4방탐색 시 다음과 같이 비용이 들 것이다.

다음 4방 탐색을 하면 그 다음 노드 계층의 비용은 3으로 전부 같을 것이다. 

☞ 이런 식으로 계층 별로 비용을 같게 하는 것은 어떻게 구현해야 할까? 하나의 계층에서 4방 탐색을 통해 큐에 넣은 값들의 갯수 만큼만 다음 Loop에서 방문하며 값을 처리해야 한다. 위의 예시에서는 정중앙에서 사방 탐색 후, 미 방문 행렬이 4개가 나왔음으로, 2 번째 Loop에서는 4번의 반복만 계산해야 한다.

이런 식으로 계층 별로 동일한 비용이 계산되도록 하면은 맨 끝 점인 [N-1] [M-1] 행렬을 조회하면, 최소 비용으로 끝 점까지 왔을 때의 비용이 나온다.

3. 코드 분석

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

public class Main {
    static int N,M;
    static int [][] miro;
    static int [] idx = new int[] {-1,0,1,0};
    static int [] idy = new int[] {0,1,0,-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());
        miro = new int [N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                miro[i][j] = Character.getNumericValue(s.charAt(j));
            }
        }
        bfs(0,0);
        System.out.println(miro[N-1][M-1]);
    }

    public static void bfs(int startX, int startY){
        ArrayDeque<Coordinate> aq1 = new ArrayDeque<>();
        aq1.add(new Coordinate(startX, startY));
        miro[startX][startY] = -1;              // 방문 처리
        int cnt = 1;
        while (!aq1.isEmpty()){
            cnt++;
            int Qsize = aq1.size();
            for (int k = 0; k < Qsize; k++) {
                Coordinate now = aq1.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = now.x + idx[i];
                    int ny = now.y + idy[i];
                    if(nx>=0 && ny>=0 && nx < N && ny < M){
                        if(miro[nx][ny] == 1){
                            miro[nx][ny] = cnt;
                            aq1.add(new Coordinate(nx,ny));
                        }
                    }
                }
            }
        }
    }
}

class Coordinate {
    int x;
    int y;

    public Coordinate (int x, int y){
        this.x = x;
        this.y = y;
    }
}

4. 성장하기

내 풀이의 경우 cnt라는 변수를 만들어, 해당 변수에 하나의 계층이 끝날 때마다 ++ 해서 비용을 계산했다. DO IT 알고리즘 책을 보니, 현재 조회 중인 행렬값 + 1 로 비용을 계산해서, 번거로이 변수를 할당하고, 변수에 ++이 되는 시점을 고민할 필요가 없게 되었다.

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

public class Main {
    static int N,M;
    static int [][] miro;
    static int [] idx = new int[] {-1,0,1,0};
    static int [] idy = new int[] {0,1,0,-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());
        miro = new int [N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                miro[i][j] = Character.getNumericValue(s.charAt(j));
            }
        }
        bfs(0,0);
        System.out.println(miro[N-1][M-1]);
    }

    public static void bfs(int startX, int startY){
        ArrayDeque<Coordinate> aq1 = new ArrayDeque<>();
        aq1.add(new Coordinate(startX, startY));
        while (!aq1.isEmpty()){
            int Qsize = aq1.size();
            for (int k = 0; k < Qsize; k++) {
                Coordinate now = aq1.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = now.x + idx[i];
                    int ny = now.y + idy[i];
                    if(nx>=0 && ny>=0 && nx < N && ny < M){
                        if(miro[nx][ny] == 1){
                            // ----- 사방 탐색 당하는 값 + 1 로 계층 비용 계산 ------
                            miro[nx][ny] = miro[now.x][now.y]+1;
                            aq1.add(new Coordinate(nx,ny));
                        }
                    }
                }
            }
        }
    }
}

class Coordinate {
    int x;
    int y;

    public Coordinate (int x, int y){
        this.x = x;
        this.y = y;
    }
}