[JAVA] 백준 2178번 - 미로 탐색

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

2178번: 미로 탐색

 

---

풀이)

 

분명 DFS 알고리즘 문제를 눌렀는데 BFS였다,,ㅋㅋㅋ

그치만 난 둘다 못하니까 괜차나~~~~

최단거리 찾는거니까 큐를 쓰는 BFS로 풀면 된다

BFS를 호출할 때마다 count를 세는 식으로 해봤는데 이상하더라고,,

그래서 찾아보니까 이전 배열 값을 늘려주는 식으로 구현하더라?

BFS가 큐에서 하나를 꺼내고 그 값 기준으로 상하좌우에서 갈 수 있는 곳을 가는데 이 때 이전 값, 즉 큐에서 꺼낸 값 기준으로 1을 더해준 값을 이동할 배열에 저장하는 것이다

언제쯤 쉬워질까 이좌식,,,

 

 

 

 

자바 코드)

import java.util.*;

public class boj2178 {
    static int n;
    static int m;
    static int[][] arr;
    static boolean[][] visited;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

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

        for(int i=0;i<n;i++) {
            String input = sc.next();
            for(int j=0;j<m;j++) {
                arr[i][j] = input.charAt(j) - '0';
            }
        }

        //(0, 0) -> (n-1, m-1)
        //최단거리 -> bfs 사용
        visited[0][0] = true; //출발지
        bfs(0, 0);
        System.out.println(arr[n-1][m-1]);

        /*for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }*/

    }

    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});

        while(!q.isEmpty()) {
            int now[] = q.poll();
            int nx = now[0];
            int ny = now[1];

            for(int i=0;i<4;i++) {
                int nextX = nx + dx[i];
                int nextY = ny + dy[i];

                if(nextX>=0 && nextX<n && nextY>=0 && nextY<m) {
                    if(arr[nextX][nextY]==1 && !visited[nextX][nextY]) {
                        q.add(new int[] {nextX, nextY});
                        visited[nextX][nextY]=true;
                        arr[nextX][nextY] = arr[nx][ny]+1;
                    }
                }
            }
        }
     }
}