54 삐약 : 백준 2178| 미로탐색 [바킹독 문제 풀이|BFS|JAVA]

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

 

package BKD_0x9_BFS;


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 BOJ_2178 {
    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());

        char[][] maze = new char[N][M]; // 입력되는 미로 값을 저장할 2차원 배열
        int[][] dist = new int[N][M];

        int[] dx = {1,0,-1,0}; // 상하좌우 계산할 x 좌표
        int[] dy = {0,1,0,-1}; // 상하좌우 계산 할 y 좌표

        Queue<Pair> q = new LinkedList<>();

        for(int i=0;i<N; i++){
            String input_str = br.readLine();
            for(int j=0;j<M;j++){
                maze[i][j] = input_str.charAt(j);
                dist[i][j] = -1; // 방문 여부 확인
            }
        }
        // 거리탐색 시작
        q.offer(new Pair(0,0));
        dist[0][0] =0;

        while(!q.isEmpty()){
            Pair p = q.poll();

            for(int i=0;i<4;i++){
                int nX = p.x + dx[i];
                int nY = p.y + dy[i];

                if(nX<0 || nX >=N || nY<0 || nY>=M) continue;

                if(maze[nX][nY] =='0' || dist[nX][nY] != -1) continue;

                q.offer(new Pair(nX,nY));
                dist[nX][nY] = dist[p.x][p.y] + 1;
            }

        }
        System.out.println(dist[N-1][M-1]+1);

        br.close();


    }
    public static class Pair{
        int x,y;

        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

 

 

 

bsf로 최단거리의 수를 구하는 방법

시작지점으로부터 모든 칸의 거리를 계산하여 또 다른 배열에 저장한다. 

 

그래프 이동 조건

• dx ={1,0,-1,0} / dy={0,1,0,-1}
• 일반적인 함수 사분면을 생각하고 x가 x축을 의미하는 가로라고 착각하기 쉬우나 x는 세로축, y는 가로축을 의미한다.
  • dist[x][y]를 생각하면 수월하다. 
• 즉 dx,dy를 사용하여 주변 탐색 시 상->우->하->좌 시계방향으로 탐색이 진행됨을 알 수 있다.

 

 

최단거리를 구하는 문제에서 dfs를 대개 사용하지 않는 이유

• 시간초과가 발생 
• 분기점이 생길 때 마다 끝까지 파고들었다가 다시 돌아오는 번거로움이 존재한다
• 즉 bfs는 한 번 지나간 노드를 다시 방문하지 않지만 dfs는 재방문 가능성이 존재하기 때문에 효율성이 떨어진다. 

 

 

 

 

참고 url : https://iseunghan.tistory.com/312

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

https://velog.io/@warmsy/%EB%B0%B1%EC%A4%80-2178%EB%B2%88-%EB%AF%B8%EB%A1%9C%ED%83%90%EC%83%89-java

[백준] 2178번 미로탐색 (java)