[백준] 2178. 미로 탐색 (JAVA)

이번에 풀어 볼 문제는 < 백준 2178번. 미로 탐색 > 이다.

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

📌 문제 탐색하기

목표

(1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸의 수 구하기 (시작위치와 도착위치도 칸을 셀 때 포함할 것)

해야 할 것

1. 미로의 정보를 어떤 식으로 저장할까?

2. 이동해야 하는 최소 칸 수를 어떻게 구하지?

입력

[첫줄] 행의 개수 : N , 열의 개수 : M ( 2 ≤ N, M ≤ 100 )

[둘째줄 ~ n+1줄] 미로

아이디어

1. 미로의 정보를 어떤 식으로 저장할까?

➡️N행 M열의 2차원 배열로 저장한다.

int[][] map = new int[N][M];

➡️해당 칸의 상,하,좌,우 에 인접한 1이 있으면 그 칸(노드)은 연결된 것으로 치는 일종의 그래프로 이해할 수 있다.

 

2. 이동해야 하는 최소 칸 수를 어떻게 구하지?

➡️ 출발 위치에서 목적지까지 도달해야 하는 "최소" 칸을 구해야 하므로 bfs 로 푸는 것이 적합해보인다.

*dfs의 경우 최단경로를 보장하지 않기 때문

➡️ 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다고 했으니, 이 부분은 고려할 필요없다.

➡️ 칸을 셀 때 시작 위치와 도착 위치도 포함하는 것 유의하자.

 

➡️ 해당 칸의 상,하, 좌, 우 를 살펴봐야 하므로 4가지 방향 벡터를 배열로 저장해놓고 풀자.

기존의 좌표가 (x,y) 라고 했을 때, 해당 좌표의 상,하,좌,우의 좌표는 아래와 같다.

 

상 : ( x+1, y+0 )

하 : ( x-1,  y+0 )

좌 : ( x+0 , y-1 )

우 : ( x+0, y+1 )

 

시계 방향으로, 각각 원래 좌표에 몇을 더하는 것이 좋을 지 조합하기 위해서 다음과 같이 방향 벡터를 만들어 놓는다.

int[] dx = new int[]{-1,0,1,0}; //x좌표의 변화를 시계방향(상,우,하,좌) 순서에 맞게 배열에 넣어둔 것
int[] dy = new int[]{0,1,0,-1}; //y좌표의 변화를 시계방향(상,우,하,좌) 순서에 맞게 배열에 넣어둔 것

 

이렇게 방향 벡터를 미리 배열로 만들어두면, 인접한 노드를 탐색할 때 반복문을 사용해서 보다 쉽게 구현할 수 있다.

📌 코드 설계하기

1. 입력으로 주어진 미로를 2차원 배열 형태로 저장한다.

2. bfs를 시행하기 위해 자료구조를 초기화한다.

- boolean visited[n][m] 배열 초기화

- bfs를 실행할 큐

- 깊이를 출력해야 하므로 깊이를 저장할 배열도 만들어둔다.

3. 시작 노드를 (0,0) 로하여 bfs 방식으로 탐색을 시행한다. ( 배열의 인덱스는 0부터 시작하는 것 유의하기 )

- 시작 노드를 큐에 넣고 방문한 것으로 기록한다. 깊이 배열에서 시작 노드의 깊이를 1로 설정한다.

- while( 큐에 남은 원소가 없을 때까지 ) {

     - 큐에서 poll을 한다. = 현재 노드
     - if ( (N,M) 노드를 만나면 ) { 탐색을 종료하고 그때의 level을 출력한다. }
     - poll한 노드와 인접한 노드 중 아직 방문하지 않은 노드를 큐에 넣는다. 이때, 큐에 들어간 노드들은 방문한 것으로 기록한다.

     - 인접한 노드의 깊이를 현재 노드의 깊이 + 1 로 업데이트 한다.

     - 만약 큐에서 poll한 원소가 (N-1,M-1)이라면 탐색을 종료한다.

}

📌 정답 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]);
        int M = Integer.parseInt(firstLine[1]);

        int[][] map = new int[N][M];

        // 미로 입력 받기
        for(int row = 0; row<N; row++){
            String[] line = br.readLine().split("");
            for(int col=0; col<M; col++){
                map[row][col] = Integer.parseInt(line[col]);
            }
        }

        boolean[][] visited = new boolean[N][M]; // 방문배열, 초기값 false
        Queue<int[]> queue = new ArrayDeque<>(); //(x좌표,y좌표)
        int[][] level = new int[N][M]; // 깊이를 저장할 배열


        //시작 노드 (1,1) => (0,0)
        queue.offer(new int[]{0,0});
        visited[0][0] = true;
        level[0][0] = 1;

        //방향벡터 : 상, 우, 하, 좌
        int[] dx = new int[]{-1,0,1,0};
        int[] dy = new int[]{0,1,0,-1};

        while(!queue.isEmpty()){
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for(int i=0; i<4; i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                //배열 범위 벗어나는지 체크 && 1인지 체크 && 아직 방문 안했는지 체크
                if(nx>=0 && ny>=0 && nx<N && ny<M && map[nx][ny]==1 && !visited[nx][ny]){
                    queue.offer(new int[]{nx,ny});
                    visited[nx][ny] = true;
                    level[nx][ny] = level[cx][cy] + 1; // 현재 노드의 깊이 + 1
                }
            }
        }

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


    }
}

➡️ 노드의 수 : N*M , 간선의 수 :  4*N*M

➡️ 전체 시간복잡도는 O(N*M) 

📌 알게 된 것

문제에서 미로의 시작 노드가 (1,1) 로 지정되어 있지만, 주어진 미로를 배열로 저장하면 배열의 인덱스는 0부터 시작하기 때문에 (1,1) 이 아닌 (0,0) 부터 시작해야 한다는 것 유의하자! 마찬가지로 (N,M) 노드도 배열의 (N-1,M-1) 과 매칭된다.

 

BFS 에서 노드의 깊이를 업데이트할 때, 인접한 노드를 큐에 넣으면서 깊이를 ( 현재노드 + 1 ) 로 업데이트 한다는 아이디어를 기억해두자.