[백준 2178번] 미로탐색

[백준 2178 URL]

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

이번 문제는 전형적이고 아주 쉬운 탐색문제입니다.

2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1

단순히 방문 체크를 해주는 조건에 map[row][col] == 1 인 경우에만 탐색할 수 있는 조건을 넣어줍니다.

1. 데이터를 입력받는 map, 방문처리를 위한 visited 배열을 선언합니다.

2. 행과 열, 그리고 몇번을 움직였는지 count하기 위해 Node 클래스를 선언합니다.

3. [0][0]의 위치에서 Queue를 이용하여 BFS를 수행합니다.

4. Queue에서 하나씩 꺼내면서 해당 Node의 행과 열 값이 각각 N-1과 M-1일 경우 ans에 cnt를 대입하고 답을 출력합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] dirX = { 0, 0, -1, 1 };
    public static int[] dirY = { -1, 1, 0, 0 };
    public static int[][] map;
    public static boolean[][] visited;
    public static int N, M, ans;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(str.charAt(j) + "");
            }
        }
        bfs();
        System.out.println(ans);
    }
 
    public static void bfs() {
 
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(0, 0, 1));
        visited[0][0] = true;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int cnt = node.cnt;
            
            if(row == N-1 && col == M-1) {
                ans = cnt;
                return;
            }
 
            for (int i = 0; i < 4; i++) {
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc] && map[nr][nc] == 1) {
                    q.offer(new Node(nr, nc, cnt + 1));
                    visited[nr][nc] = true;
                }
            }
 
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
 
}
 
class Node {
    int row;
    int col;
    int cnt;
 
    public Node(int row, int col, int cnt) {
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
 
}