[백준/JAVA] 2178번: 미로 탐색

🔺 문제

2178번: 미로 탐색

 

 

🔺 코드

import java.util.*;
import java.io.*;

public class Main {
    // 상하좌우 탐색 위한 배열 선언
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static boolean[][] visited;
    static int[][] A;

    static int N, M;

    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());   // row
        M = Integer.parseInt(st.nextToken());   // col

        A = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            String line = st.nextToken();

            for(int j = 0 ; j < M ; j++) {
                A[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }

        BFS(0, 0);
        System.out.println(A[N - 1][M - 1]);
    }

    // BFS 구현
    public static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {i, j});
        visited[i][j] = true;

        while(!queue.isEmpty()) {
            int now[] = queue.poll();

            // 상하좌우 탐색
            for(int k = 0 ; k < 4 ; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];

                // 좌표 유효성 검사
                if(x >= 0 && y >= 0 && x < N && y < M) {
                    if(A[x][y] != 0 && !visited[x][y]) {
                        visited[x][y] = true;
                        A[x][y] = A[now[0]][now[1]] + 1;    // 깊이 업데이트
                        queue.add(new int[] {x,y});	   // 큐에 이동한 좌표 넣기
                    }
                }
            } 
        }
    }
}

✅ 해결 아이디어
- BFS (최초 도달 깊이 계산 = 최단 거리 계산)
- 1) 상하좌우 탐색
→ 2) 좌표 유효성 검사 (숫자가 1이어야 함 & 아직 방문 X)
→ 3) 종료 지점에서 BFS 종료하며 깊이 출력

 

💥 유의사항

⇨ BFS 호출할 때마다 count하는 게 아닌, 이전 배열 값을 늘려주는 식으로 구현 (= 깊이 업데이트)

 

 

---

🔺 다른 풀이들

- 풀이1)

백준 2178번 : 미로 탐색 (JAVA) 문제 풀이

 

 

- 풀이2) 입력을 char로 받음 & 인접 행렬 char형으로

백준 2178 미로 탐색 알고리즘 자바 JAVA 풀이

 

 

- 풀이3) 상세한 해설.. 복습용!

백준 2178번 - 미로탐색 / Java

동서남북으로 방향을 설정하면 이동 가능한 가지수가 이렇게 되나보다.

어쩐지 나랑 dx dy 반대로 되어있는데도 결과가 같게 나오더라,,,!

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

---

💬 느낀 점

최단 경로 = BFS !

BFS 쉽지 않구나,,,,,

많이 풀어보는수밖에!!

 

1회독	2회독	3회독	4회독	5회독
V	5/25	6/10	6/15	8/4

 

(+ 5/25 2회독)

좀 감이 잡혔다!!!

새로 코드 작성해서 복습해봤더니 더 괜찮은 코드를 작성했나보다(?) 😆😆

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 0, -1, 1};    // 좌우
    static int[] dy = {1, -1, 0, 0};    // 상하
    
    static boolean[][] visited;
    static int[][] A;
    
    static int N, M;    
    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());
        
        visited = new boolean[N][M];
        
        A = new int[N][M];
        
        // 입력 받기
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                A[i][j] = str.charAt(j) - '0';
            }
        }
        
        BFS(0, 0);
        System.out.println(A[N - 1][M - 1]);
    }
    
    static void BFS(int x, int y) {
        visited[x][y] = true;
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            // 상하좌우 이동
            for(int d = 0 ; d < 4 ; d++) {
                int newX = now[0] + dx[d];
                int newY = now[1] + dy[d];
                
                if(0 <= newX && newX < N && 0 <= newY && newY < M && !visited[newX][newY] && A[newX][newY]!= 0) {
                    visited[newX][newY] = true;
                    A[newX][newY] = A[now[0]][now[1]] + 1;  //  깊이 업데이트
                    queue.add(new int[]{newX, newY});
                }       
            }
        }
    }
}

 

 

(+ 6/10 3회독)

아...  중간에 유효성 검사 까먹었었다... & 깊이 업데이트하는 식으로 구하는 것도 잊음..

(+ 6/15 4회독)

푼지 며칠 안되어서 그런지(?)  비교적 수월하게 작성!

 

(+ 8.4 5회독)

이제 이 정도는 쉽게 푸는 사람이 되었습니다!

감사합니다 충성충성...

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};   // 상하좌우
    static int[] dy = {1,-1,0,0};
    
    static int[][] map;
    static boolean[][] visited;
    static int N, M;
    
    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());
        
        map = new int[N + 1][M + 1];
        visited = new boolean[N + 1][M + 1];
        
        for(int i = 1 ; i <= N ; i++) {
            char[] ch = br.readLine().toCharArray();
            for(int j = 0 ; j < M ; j++) {
                map[i][j+1] = ch[j] - '0';
            }
        }
        
        bfs(1, 1);
        System.out.println(map[N][M]);
    }
    
    private static void bfs(int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a,b});
        
        visited[a][b] = true;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int x = now[0] + dx[d];
                int y = now[1] + dy[d];
                
                if(x < 1 || y < 1 || x > N || y > M || map[x][y] == 0 || visited[x][y])    continue;
                if(!visited[x][y] && map[x][y] == 1) {
                    map[x][y] = map[now[0]][now[1]] + 1;
                    queue.add(new int[]{x, y});
                }
            }
        }
    }
}

---

(참고)

✔ 인접 행렬

그래프 표현 (인접 리스트 / 인접 행렬)