[BOJ-2178][BFS] 미로 탐색 - Java

문제 바로가기

2178번: 미로 탐색

어우 10개월 전에 풀었던 건데 자바로 한 번 풀어보았씁니다.

아직 자바가 익숙치 않아 코드가 이쁘지 않기 때문에 혹시 조언해주실게 있으면 댓글에 남겨주세욥

 

BFS 문제를 풀겠다고 다짐하고 거의 처음 접한 문제였는데, 맨 처음 풀이 방법을 찾아 보고 이마를 탁 쳤던 기억이 납니다. n방문 여부만(true/false) 체크하는 문제만 봤었는데, next 좌표에 왔을 때 cur 좌표에 있는 visited 값 + 1 해서 이동 거리(혹은 시간)을 구하는 건 누가 생각한걸까여

세상엔 참 똑똑하신 분이 많습니다

 

요런 로직만 생각하면 아아아주 쉽게 풀 수 있습니다. 0이면 가지말고 1이면 가도록 해서, visited[N][M]의 값이 정답이 됩니다.

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

public class Main {
    static int N;
    static int M;
    static int [][] map;
    static int [][] visited;
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};

    public static boolean isIn(Dir dir){
        if(0<= dir.y && dir.y < N && 0<= dir.x && dir.x < M) return true;
        else return false;
    }
    //BFS
    public static int solve(){
        int ans = 0;
        Queue<Dir> q = new LinkedList<>();

        q.offer(new Dir(0, 0));
        visited[0][0] = 1;

        while(!q.isEmpty()){
            Dir cur = new Dir(q.peek().y, q.peek().x);
            q.poll();

            for(int i=0;i<4;i++){
                Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
                if(!isIn(next)) continue;
                if(visited[next.y][next.x] != 0) continue;
                if(map[next.y][next.x] != 1) continue;

                q.offer(next);
                visited[next.y][next.x] = visited[cur.y][cur.x] + 1;
            }
        }

        ans = visited[N-1][M-1];
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Scanner input = new Scanner(System.in);
        N = input.nextInt();
        M = input.nextInt();
        map = new int[N][M];
        visited = new int[N][M];

        for(int i=0;i<N;i++){
            String temp = input.next();
            for(int j=0;j<M;j++){
                map[i][j] = temp.charAt(j)-'0';
                visited[i][j] = 0;
            }
        }

        System.out.print(solve());
    }
}

Dir: 좌표 클래스입니다. 코드가 쪼까 더러워지지 않나 고민도 했는데 낫배드한 거 같슴다
isIn: 좌표가 map 밖으로 튀어나가는지 확인해주는 메소드입니다.

 

2차원 map에서 상하좌우 네 방향만 체크해주면서 1이면 이동하고, 0이면 가지않도록 해서 끝까지 따라가주면 됩니다.

 

감사합니다.