백준 2178번 : 미로탐색 자바

백준 2178번

2178번: 미로 탐색

 

문제

---

 

풀이

---

BFS를 사용하여 풀었다. 

시작점이 (0,0)으로 고정되어있고 각 칸과 칸 사이의 거리는 동일하고 이동할 수 있는 칸들은 서로 연결되어 있기 때문에

결국에는 미로를 그래프로써 본다면 (N,M)까지 가는 거리는 그 높이만큼이 거리라고 볼 수 있다. 

 

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    static int[][] graph;
    static boolean cheked[][];
    static int N,M;

    static int[] leftright = {1, -1, 0, 0};
    static int[] updown = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new int[N][M];
        cheked = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                graph[i][j] = line.charAt(j) - '0';
            }
        }

        cheked[0][0] = true;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});


        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int i = 0; i < 4; i++) {


                int pre = graph[node[0]][node[1]];
                int x = node[0] + leftright[i];
                int y = node[1] + updown[i];


                if (x < 0 || y < 0) {
                    continue;
                }
                if (x >= N || y >= M) {
                    continue;
                }

                if (!cheked[x][y] && graph[x][y] == 1) {

                    cheked[x][y] = true;
                    queue.add(new int[]{x,y});
                    graph[x][y] = pre + 1;
                }
            }

        }

        System.out.println(graph[N-1][M-1]);

    }


}

 

 

이런 그래프 문제를 처음 접해서 그런지 오래걸렸다...

무엇보다 자꾸 사소한 변수 초기화 실수로 삽질을 많이 했다. 

이번 문제를 토대로 DFS/BFS의에 대한 기반이 좀 더 다져진것 같다.