[백준] 2178 미로 탐색 자바 BFS 문제 풀이 및 정답

문제 요약)

- 세로 n, 가로 m이 주어짐

- 출발위치에서 마지막 위치의 최소거리

 

주의점)

- x

 

풀이)

BFS로 풀이를 진행하며 q를 사용할때 x, y등 좌표값을 줘야하기 때문에 class를 선언해주거나 배열자체를 q에 넣어야하는데 별도 클래스를 만드는 것보다 배열이 조금 더 편해서 배열로 풀이했습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Maze2178_blog {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map;
    static int[][] distance;
    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());

        // 첫 위치가 1,1이니까 인덱스가 1부터 잡히게 +1해주기
        map = new int[n+1][m+1];
        distance = new int[n+1][m+1];

        // map 채워주기
        for (int i=1; i<=n; i++) {
            String[] strs = br.readLine().split("");
            int j = 1;
            for (String a : strs) {
                map[i][j] = Integer.parseInt(a);
                j++;
            }
        }

        distance[1][1] = 1;
        BFS(1, 1);
        System.out.println(distance[n][m]);
    }

    static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        while(!q.isEmpty()) {
            int[] current = q.poll();

            for (int k=0; k<4; k++) {
                int nx = current[0] + dx[k];
                int ny = current[1] + dy[k];
                // out of index 방지
                if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
                // 이미 방문했거나(dis가 0이상이면 방문했다는 것) 방문 불가한 곳 제외
                if (distance[nx][ny] > 0 || map[nx][ny] == 0) continue;
                // q에 넣고 거리 세팅해주기
                q.offer(new int[] {nx, ny});
                distance[nx][ny] = distance[current[0]][current[1]] + 1;
            }
        }
    }
}