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

 

📝문제 설명

 

- 배열의 시작인 인덱스값 [0,0]에서 배열의 끝인 인덱스값 [3,5]까지의 최단거리를 구하는 문제

- 최단 거리 문제는 무조건 BFS로 풀어야한다. DFS로 풀면 시간초과남

---

📢입출력 예시

 

---

✏️문제 풀이

다양한 풀이 방법 터득을 위해 클래스를 사용한 방법과 배열을 사용한 방법 두가지로 풀어 보았다.

 

클래스 사용 풀이

package Baekjoon.Graph.BFS;

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

public class Baek2178 {

    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N, M;
    
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

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

        map = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];

        for(int i=1; i<N+1; i++){
            String str = bufferedReader.readLine();
            for(int j=1; j<M+1; j++){
                char c = str.charAt(j-1);
                map[i][j] = c - '0';
            }
        }

        int dist = BFS();

        System.out.println(dist);

    }

    private static int BFS(){
        Queue<spot> queue = new LinkedList<>();

        queue.offer(new spot(1,1,1));
        visited[0][0] = true;
        count = 1;

        while(!queue.isEmpty()){
            spot s = queue.poll();
            int currentX = s.x;
            int currentY = s.y;
            int currentDist = s.dist;

            for(int i=0; i<4; i++){
                int newX = currentX + dx[i];
                int newY = currentY + dy[i];

                if(newX == N && newY == M){
                    return currentDist+1;
                }

                if(newX >= 1 && newY >= 1 && newY <= M && newX <= N){
                    if(map[newX][newY] == 1 && !visited[newX][newY]){
                        visited[newX][newY] = true;
                        queue.offer(new spot(newX, newY, currentDist+1));
                    }
                }
            }
        }
        return -1;
    }
}


class spot{
    int x;
    int y;
    int dist;
    spot(int x, int y, int dist){
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}

배열 사용 풀이

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

public class Baek2178 {

    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N, M;
    
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

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

        map = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];

        for(int i=1; i<N+1; i++){
            String str = bufferedReader.readLine();
            for(int j=1; j<M+1; j++){
                char c = str.charAt(j-1);
                map[i][j] = c - '0';
            }
        }

        System.out.println(BFS());

    }

    private static int BFS(){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1,1,1});
        visited[1][1] = true;

        while(!queue.isEmpty()){
            int[] node = queue.poll();
            int currentX = node[0];
            int currentY = node[1];
            int currentDist = node[2];

            if(currentX == N && currentY == M){
                return currentDist;
            }

            for(int i=0; i<4; i++){
                int newX = currentX + dx[i];
                int newY = currentY + dy[i];

                if(newX >= 0 && newY >= 0 && newX <= N && newY <= M){
                    if(map[newX][newY] == 1 && !visited[newX][newY]){
                        queue.offer(new int[]{newX, newY, currentDist+1});
                        visited[newX][newY] = true;
                    }
                }
            }
        }

        return -1;
    }
}

---

💡새로 알게된 점

 

---