[BOJ_4963] 미로 탐색(java)

문제

• 1 : 이동할 수 있는 칸, 0 : 이동할 수 없는 칸
• (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램

조건

• 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동 가능
• 각각의 수들은 붙어서 입력으로 주어짐

어려웠던 점

• 이동 할 때 최소 칸 수 계산하는 방법 구현

1. 최소 칸 수 계산

• visited 배열을 방문체크로만 사용하는 것이 아니라 이동할 때 이전에 이동했던 칸 수 + 1 하여 최소 이동 칸 수 계산으로 활용한다.

전체코드

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

public class BOJ_2178 {

    static int[] dx = {-1, 1, 0, 0}; // 상 하 좌 우
    static int[] dy = {0, 0, -1, 1};

    static int N; // N : 열
    static int M; // M : 행
    static int[][] map;
    static int[][] visited;
    static String str;

    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());

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

        for(int i = 0; i < N; i++){
            str = br.readLine();
            for(int j = 0; j < M; j++){
                map[i][j] = str.charAt(j)- '0';
            }
        }
        System.out.println(bfs(0,0));
    }

    public static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x,y});
        visited[x][y] = 1;

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

            if(cx == N - 1 && cy == M - 1){
                return visited[cx][cy];
            }

            for(int i = 0; i < 4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if(nx < 0 || ny < 0 || nx >= N || ny >= M){
                    continue;
                }
                if(map[nx][ny] == 0 || visited[nx][ny] != 0){
                    continue;
                }
                queue.offer(new int[]{nx,ny});
                visited[nx][ny] = visited[cx][cy] + 1;
            }
        }
        return -1;
    }
}

느낀점

• 이동 칸 수나 어떤 계산을 수행해야할 때 count 변수로 계산했는데 visited 배열을 활용해서 최소 이동 칸 수를 계산할 수 있다는 것을 새롭게 알게 되었다.