백준 온라인 저지 - 2178번: 미로 탐색

🔍 문제

---

 

2178번: 미로 탐색

 

✏️ 풀이 - Java

---

 

최단 거리를 구하는 문제여서 bfs로 풀게 되었다. 처음에 bfs탐색으로 풀었을 때 모든 지점을 bfs로 탐색하기는 탐색하는데 최단거리를 구하지를 못해서 굉장히 많은 시간을 허비했다. 풀고보니까 아니 이걸 왜 이렇게 생각못했냐고!!!!!!!하는 자괴감이 들었다...하....

 

어쨌든 풀고나니까 언제 그랬냐는 듯이 속시원

 

 

그래도 이 맛에 코딩합니다...
어쨌든 풀이는 아래와 같다. 어떤 좌표 값으로 오기까지의 거리는 현재 좌표 이전 좌표까지의 거리 + 1이다. maze 배열은 어차피 한번 방문하고나면 값을 안쓰므로 dist[][]라는 거리용 배열을 새로 만들까 했으나 그냥 방문한 좌표 값에 다시 거리를 넣어주어서 재활용(?)했다. 찾아보니 n, m 값은 어차피 2~100사이여서 이를 고려하지 않고 애초에 maze배열 초기화 할때부터 maze[100][100]로 만드시는 분들도 있었다.

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

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] maze = new int[n][m]; // 입력 값 

        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < m; j++) {
                maze[i][j] = s.charAt(j) - '0';
            }
        }

        System.out.print(bfs(n, m, maze));

    }

    private static int bfs(int n, int m, int[][] maze) {
        int[] dx = {1, -1, 0, 0,}; //상, 하, 좌, 우 
        int[] dy = {0, 0, -1, 1}; 

        Queue<int[]> q = new LinkedList<>();
        boolean[][] c = new boolean[n][m];//방문체크 배열 c

        q.add(new int[]{0, 0}); //0, 0번 좌표 큐에 넣
        c[0][0] = true; //0, 0번 좌표 방문 체

        while(!q.isEmpty()) {

            int[] current = q.poll();

            int x = current[0];
            int y = current[1];

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

                if(nx >= 0 && nx < n && ny >= 0 && ny < m) { // nx, ny값이 유효한 값일 때만

                    if(maze[nx][ny] == 1 && !c[nx][ny]) {

                        c[nx][ny] = true;
                        maze[nx][ny] = maze[x][y] + 1; //이전 좌표의 거리수 + 1
                                                        //한번 방문한 maze 배열 값은 거리 수로 바꿔준다.
                        q.add(new int[]{nx, ny});

                    }

                }

            }

        }

        return maze[n-1][m-1];
    }

}