[백준]2178: 미로 탐색 (BFS 풀이)

정말 힘든 싸움이었다. 며칠동안 머리를 끙끙 앓았고 나에게 BFS에 대한 길을 뚫어준 문제. 최단 거리 문제에 대한 감각을 키워나가자!

---

 

정말 너무 뿌듯한 문제였다. 나는 이 문제를 접근할때 자꾸 DFS, 재귀로 접근을 했다. 

 

public static void isSafeR(int x, int y, int countR, boolean[][] visited) {
    if (x == N - 1 && y == M - 1) {
        if (countR < ans) ans = countR;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int newX = x;
        int newY = y;
        newX += row[i];
        newY += col[i];
        if (newX >= 0 && newY >= 0) {
            if ((newX < N && newY < M) && Mirro[newX][newY] == 1 && !visited[newX][newY]) {
                visited[x][y] = true;
                isSafeR(newX, newY, countR + 1,visited);
                visited[x][y] = false;
            }
        }
    }
}

 

하지만 재귀로 풀어보니 막상 cnt를 어떻게 구해야할지, 최단 거리인데 한곳만 파고 들어가다가 끝이 나버리면은 그 길이 최단 거리가 아님에도 끝이나서 최단거리를 제대로 구하지 못하고....... 어찌저찌해서 코드를 완성을 했다고 쳐도 재귀 방식은 시간 초과가 났었기 때문에 생각의 회로를 완전히 바꾸게 되었다. BFS로...

정답 코드

package graph;

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

public class Q2178 {
    static int N, M;
    static int[] row = {0, 0, 1, -1};
    static int[] col = {1, -1, 0, 0};
    static Queue<Integer> queue;

    public static boolean isSafe(int[][] arr, int x, int y, boolean[][] visited) {
        if ((x >= 0 && y >= 0) && (x < N && y < M)) {
            if (!visited[x][y] && arr[x][y] == 1) {
                return true;
            }
        }
        return false;
    }

    public static void BFS(int[][] arr, int x, int y, boolean[][] visited) {
        queue.offer(x);
        queue.offer(y);
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            x = queue.poll();
            y = queue.poll();

            for (int i = 0; i < 4; i++) {
                int newX = x + row[i];
                int newY = y + col[i];
                if (isSafe(arr, newX, newY, visited)) {
                    queue.offer(newX);
                    queue.offer(newY);
                    visited[newX][newY] = true;
                    arr[newX][newY] = arr[x][y] + 1;
                }
            }
        }
    }

    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());
        int[][] arr = new int[N][M];
        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(String.valueOf(line.charAt(j)));
            }
        }
        queue = new ArrayDeque<>();
        BFS(arr, 0, 0, visited);
        System.out.println(arr[N - 1][M - 1]);

    }
}

 

---

    static int N, M;
    static int[] row = {0, 0, 1, -1};
    static int[] col = {1, -1, 0, 0};
    static Queue<Integer> queue;

    public static boolean isSafe(int[][] arr, int x, int y, boolean[][] visited) {
        if ((x >= 0 && y >= 0) && (x < N && y < M)) {
            if (!visited[x][y] && arr[x][y] == 1) {
                return true;
            }
        }
        return false;
    }

    public static void BFS(int[][] arr, int x, int y, boolean[][] visited) {
        queue.offer(x);
        queue.offer(y);
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            x = queue.poll();
            y = queue.poll();

            for (int i = 0; i < 4; i++) {
                int newX = x + row[i];
                int newY = y + col[i];
                if (isSafe(arr, newX, newY, visited)) {
                    queue.offer(newX);
                    queue.offer(newY);
                    visited[newX][newY] = true;
                    arr[newX][newY] = arr[x][y] + 1;
                }
            }
        }
    }

우선 isSafe 함수로 길이 있는지 여부를 판단해주었다.

->

길의 좌표가 정상적인 범주 내에 있으면서, visit하지 않았고, 길이 존재해야함(값이 1)!

 

그 이후에 que를 활용하여 BFS를 구현했다.

x좌표와 y좌표를 순서대로 offer해서 넣어줬지만,,,,,,, 이런 개판인 코드는 버려야할 듯;;;; Node를 만들어서 객체 넣는 연습 하자 꼮!

 

->

while문으로 들어가 보자. que가 비어있을때까지 반복을 한다.

->

x와 y에 que에 들어있는 좌표들을 poll해서 초기화 시켜준다.

->

for 문에서는 static으로 선언한 row, col 증감값들을 더해준 뒤 isSafe로 검사를 해준다.

->

검사 한 값이 정상적으로 통과가 된다면 그 값을 다시 offer해주고, visit 처리를 해준다!!!(일반적인 BFS)

->

여기가 중요.

newX,newY 좌표의 값을 현재 위치한 좌표의 값에 +1을 해준다!!!!!!!!!!!!!!

이게 무슨 뜻이냐면,,,,

초기에 모든 길들은 값이 1이다.

한 칸 이동할때마다 앞칸보다 거리가 1이 증가 하는 것이므로

길이 존재한다==해당 좌표의 값이 1이다!! -> 이동가능하다!!!(visited 배열 방문 처리) -> 그 좌표의 값을 누적 거리로 업데이트를 시킨다!!!!!

->

이렇게 한다면, 결승점에 결국에는 최단거리의 길이가 제일 먼저 입력이 된다!!!

그렇게 되면, 삥 돌아서 오는 다른 길들은 이미 visit 처리가 되어있는 끝점에 도달하지 못하고 그냥 poll이 되어서 BFS가 종료된다.

 

 

---

그렇게 해서 맨 마지막 좌표의 값을 출력해준다면???????????????-> 그 값이 곧, 최단 거리!!!!!!!!

지린당,,,,

---