[백준] 2178번(Java)

📖 미로 탐색

[ 문제 ]

• N×M크기의 배열로 표현되는 미로가 있다.
• 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
• 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

---

💡풀이

• 해당 문제는 BFS로 접근해 해결했다.
• 현재 방문 노드의 상하좌우 칸을 하나씩 검사해 Queue에 넗는 방식으로 구현했으며, 큐에는 {row 값, col 값, 탐색 횟수}가 입력되도록 설정했다.
• 현재 노드를 기준으로 다음 노드가 방문한 이력이 있는지, 그래프 범위 내에 있는지, 값이 1인지를 확인해 큐에 담았고, Queue가 비게 되거나, 원하는 위치에 도달하는 경우 반복문을 종료하고 값을 출력하도록 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int[][] graph;  // 그래프
    static boolean[][] visited;  // 방문한 위치 확인
    static int[][] dr;   // 방향을 담는 배열

    static int num; 
    static int N;
    static int M;

    public static void main(String[] args) throws IOException {
        // 방향 초기화
        dr = new int[][]{{1,0},{-1,0}, {0, 1}, {0, -1}};

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 가로 길이
        M = Integer.parseInt(st.nextToken()); // 세로 길이

        graph = new int[N][M];
        visited = new boolean[N][M];

        // graph 정리
        for(int i = 0 ; i < N ; i ++){
            String[] str = br.readLine().split("");
            for(int j = 0 ; j < M ; j ++){
                graph[i][j] = Integer.parseInt(str[j]);
            }
        }
        
        bfs(0, 0);

    }

    public static void bfs(int r, int c){
        visited[r][c] = true;
        Queue<int[]> tmp = new ArrayDeque<>();
        tmp.add(new int[]{r, c, 1});

        while(!tmp.isEmpty()){
            int[] cur = tmp.poll();
            int cr = cur[0];
            int cc = cur[1];
            int cnt = cur[2];
            if(cr == N - 1 && cc == M - 1){
                System.out.println(cnt);
                break;
            }

            for(int i = 0 ; i < 4 ; i ++){
                if(isVal(cr + dr[i][0], cc + dr[i][1]) && !visited[cr + dr[i][0]][cc + dr[i][1]] && graph[cr + dr[i][0]][cc + dr[i][1]] == 1){
                    visited[cr + dr[i][0]][cc + dr[i][1]] = true;
                    tmp.add(new int[]{cr + dr[i][0], cc + dr[i][1], cnt + 1});
                }
            }
        }
    }
    public static boolean isVal(int r, int c){
        // r,c 가 그래프 범위 내에 있는지?
        return 0 <= r && r < N && 0 <= c && c < M;
    }
}

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