[BAEKJOON] - 2178번 : 미로 탐색

2178번 문제 링크

⌛ 시간 복잡도

• 최대 갯수 제한이 100이므로, 시간 복잡도는 여유가 있다.

📜 로직

• DFS보다 BFS가 적합한 이유는 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문이다.

1. 방문 배열과 깊이를 나타내는 배열을 선언한다.
2. 현재 노드에 상하좌우로 인접한 노드를 확인하기 위해 아래 배열을 선언한다.

	static int[] dr = {0,1,-1,0};
    static int[] dc = {1,0,0,-1};

3. 깊이 배열에 미로의 값으로 초기화 해준 뒤, BFS를 통해 탐색 및 깊이를 측정한다.
4. 미로의 도착지점에 깊이를 출력한다.

😀 성공

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

public class Main{
    static boolean[][] visited;
    static int[][] arr;
    static int[] dr = {0,1,-1,0};
    static int[] dc = {1,0,0,-1};
    static int n,m;
    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()); // 열 |
        
        visited = new boolean[n][m];
        arr = new int[n][m];
        
        for(int i=0; i<n; i++){
            String str = br.readLine();
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(str.charAt(j) + "");
            }
        }
        br.close();
        
        bfs(0,0);
        
        System.out.println(arr[n-1][m-1]);
    }
    
    static void bfs(int r, int c){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {r,c});
        visited[r][c] = true;
        
        while(!queue.isEmpty()){
            int[] now= queue.poll();
            
            for(int i=0; i<4; i++){
                int tmp_row = now[0] + dr[i];
                int tmp_col = now[1] + dc[i];
                
                if(tmp_row >= 0 && tmp_col >= 0 && tmp_row < n && tmp_col < m){
                    if(arr[tmp_row][tmp_col] != 0 && !visited[tmp_row][tmp_col]){
                        visited[tmp_row][tmp_col] = true;
                        arr[tmp_row][tmp_col] = arr[now[0]][now[1]] + 1;
                        queue.offer(new int[] {tmp_row, tmp_col});
                    }
                }
            }
        }
    }
}