[백준 / Java] 2178번 미로 탐색

사용한 알고리즘 (BFS)

BFS

https://cobi-98.tistory.com/36

[필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해

 

🔒 2178번 미로 탐색

✔ 문제 설명

🚩 요구사항 분석

• int [ ][ ] N, M 미로 생성
• 상하좌우로 이동할 수 있는 배열(dx, dy) 생성
• 방문 체크 boolean 배열
• 이동할 수 없는 경우 ( 0 , 방문한 경우, 미로 밖으로 나가는 경우) 조건 
• while 문으로 현재 값 poll()
• 이동할 수 있는 경우 큐에 넣기
• 도착위치까지 반복

 

🔑 문제풀이

요구사항을 분석한 대로 상하좌우로 이동하는 배열을 돌려서,

조건 ( 이동할 수 없는 경우면 ) continue;

이동할 수 있으면 queue 에 담으면서 도착위치로 너비 우선 탐색을 해 나간다.

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 Main {
    public static int N;
    public static int M;
    public static int[][] maze;
    public static int count;
    public static boolean[][] visit;
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};


    public static Queue<int[]> queue = new LinkedList<>();


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

        maze = new int[N][M];
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String st2 = br.readLine();
            for (int j = 0; j < M; j++) {
                maze[i][j] = st2.charAt(j) - '0';
            }
        }
        visit[0][0] = true;
        bfs(0,0);
        System.out.println(maze[N-1][M-1]);

    }

    public static void bfs(int x, int y) {
        queue.add(new int[] {x,y});

        while(!queue.isEmpty()) {
            int now[] = queue.poll();
            int nowX = now[0];
            int nowY = now[1];

            for(int i=0; i<4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
                    continue;
                if (visit[nextX][nextY] || maze[nextX][nextY] == 0)
                    continue;

                queue.add(new int[] {nextX, nextY});
                maze[nextX][nextY] = maze[nowX][nowY] + 1;
                visit[nextX][nextY] = true;
            }
        }
    }
}