백준 2178번 : 미로 탐색(Java)

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

2178번: 미로 탐색

 

 

---

[풀이]

 

 BFS, DFS 관련해서 공부하는 과정에서 풀어본 기본 문제이다. 기본 문제인 것같은데도... 푸는데 쉽지가 않았고 오래 걸렸다. BFS를 큐로 구현해서 풀었으며 지나가는 곳을 visited 배열과 arr 배열을 통해서 조건을 확인하며 풀어나갔다. 아무래도 BFS와 DFS 기본 문제이기에 해당 알고리즘을 잘 구현하기만 하면 풀 수 있었던 것 같다. 얼른 코테 잘해지고 싶다.. 공부하자...

 

---

[코드]

 

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

class Main {
    static int n, m;
    static boolean[][] visited;
    static int[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String s = bufferedReader.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String line = bufferedReader.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }

        bfs(0, 0);
        System.out.println(arr[n - 1][m - 1]);
    }

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

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int now_x = now.x + dx[i];
                int now_y = now.y + dy[i];

                if (now_x >= 0 && now_x < n && now_y >= 0 && now_y < m) {
                    if (visited[now_x][now_y] == false && arr[now_x][now_y] == 1) {
                        queue.offer(new Node(now_x, now_y));
                        arr[now_x][now_y] = arr[now.x][now.y] + 1;
                        visited[now_x][now_y] = true;
                    }
                }
            }
        }
    }
}