[백준 2178 java 자바] 미로 탐색 (BFS/DFS)

[Silver I] 미로 탐색 - 2178

문제 링크

성능 요약

메모리: 15132 KB, 시간: 196 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

---

코드

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

public class Main {
    static int n,m;
    static int[][] graph;
    static boolean[][] visited;
    static String[] strs;
    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 br = new BufferedReader(new InputStreamReader(System.in));
        strs = br.readLine().split(" ");
        n = Integer.parseInt(strs[0]);
        m = Integer.parseInt(strs[1]);

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

        //그래프 초기화
        for (int i = 0; i < n; i++) {
            strs = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(strs[j]);
            }
        }

        bfs(0, 0);

        System.out.println(graph[n-1][m-1]);
    }

    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        visited[x][y] = true;
        while (!q.isEmpty()) {
            Node node = q.poll();

            for (int i = 0; i < 4; i++) {
                int nX = dx[i] + node.x;
                int nY = dy[i] + node.y;
                if(nX < 0 || nX >= n || nY < 0 || nY >= m) continue;
                if (!visited[nX][nY] && graph[nX][nY] != 0) {
                    graph[nX][nY] = graph[node.x][node.y] + 1;
                    visited[nX][nY] = true;
                    for (int k = 0; k < n; k++) {
                        for (int j = 0; j < m; j++) {
                            System.out.print(graph[k][j]+"|");
                        }
                        System.out.println();
                    }
                    System.out.println("================");
                    q.offer(new Node(nX, nY));
                }

            }
        }
    }
}

---

코드 분석

변수선언

       static int n,m;//가로 세로
    static int[][] graph;//지도
    static boolean[][] visited;//방문 체크
    static String[] strs;
    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;
        }
    }

기본 Main

     public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));//입력 받기
        strs = br.readLine().split(" ");
        n = Integer.parseInt(strs[0]);
        m = Integer.parseInt(strs[1]);

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

        //그래프 초기화
        for (int i = 0; i < n; i++) {
            strs = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(strs[j]);
            }
        }

        bfs(0, 0);

        System.out.println(graph[n-1][m-1]);
    }

• bfs(0, 0); : 1회에 뻗어가면서 최종 목적지까지 가면 되므로 1번만 실행한다.

bfs

/*
    너비 우선 탐색으로 방문하지 않은 인접 노드들의 값을 바로 직전 값 +1로 해준다.
*/

    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        visited[x][y] = true;
        while (!q.isEmpty()) {
            Node node = q.poll();

            for (int i = 0; i < 4; i++) {
                int nX = dx[i] + node.x;
                int nY = dy[i] + node.y;
                if(nX < 0 || nX >= n || nY < 0 || nY >= m) continue;
                if (!visited[nX][nY] && graph[nX][nY] != 0) {
                    graph[nX][nY] = graph[node.x][node.y] + 1;
                    visited[nX][nY] = true;
                    for (int k = 0; k < n; k++) {
                        for (int j = 0; j < m; j++) {
                            System.out.print(graph[k][j]+"|");
                        }
                        System.out.println();
                    }
                    System.out.println("================");
                    q.offer(new Node(nX, nY));
                }

            }

입력 예시

4 6
101111
101010
101011
111011
1|0|1|1|1|1|
2|0|1|0|1|0|
1|0|1|0|1|1|
1|1|1|0|1|1|
================
1|0|1|1|1|1|
2|0|1|0|1|0|
3|0|1|0|1|1|
1|1|1|0|1|1|
================
1|0|1|1|1|1|
2|0|1|0|1|0|
3|0|1|0|1|1|
4|1|1|0|1|1|
================
1|0|1|1|1|1|
2|0|1|0|1|0|
3|0|1|0|1|1|
4|5|1|0|1|1|
================
1|0|1|1|1|1|
2|0|1|0|1|0|
3|0|1|0|1|1|
4|5|6|0|1|1|
================
1|0|1|1|1|1|
2|0|1|0|1|0|
3|0|7|0|1|1|
4|5|6|0|1|1|
================
1|0|1|1|1|1|
2|0|8|0|1|0|
3|0|7|0|1|1|
4|5|6|0|1|1|
================
1|0|9|1|1|1|
2|0|8|0|1|0|
3|0|7|0|1|1|
4|5|6|0|1|1|
================
1|0|9|10|1|1|
2|0|8|0|1|0|
3|0|7|0|1|1|
4|5|6|0|1|1|
================
1|0|9|10|11|1|
2|0|8|0|1|0|
3|0|7|0|1|1|
4|5|6|0|1|1|
================
1|0|9|10|11|1|
2|0|8|0|12|0|
3|0|7|0|1|1|
4|5|6|0|1|1|
================
1|0|9|10|11|12|
2|0|8|0|12|0|
3|0|7|0|1|1|
4|5|6|0|1|1|
================
1|0|9|10|11|12|
2|0|8|0|12|0|
3|0|7|0|13|1|
4|5|6|0|1|1|
================
1|0|9|10|11|12|
2|0|8|0|12|0|
3|0|7|0|13|1|
4|5|6|0|14|1|
================
1|0|9|10|11|12|
2|0|8|0|12|0|
3|0|7|0|13|14|
4|5|6|0|14|1|
================
1|0|9|10|11|12|
2|0|8|0|12|0|
3|0|7|0|13|14|
4|5|6|0|14|15|
================
15

Process finished with exit code 0