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

 

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

 

백준 2178 미로 탐색 알고리즘은 완전탐색인 BFS 알고리즘으로 풀어야 하는 문제다. 상하좌우로 움직일 수 있고, 입력단에서 주어지는 N,M 좌표까지 가장 최단거리로 움직이는 수를 구하는 문제다. 최초 시작점인 (0,0) 좌표와 마지막 도착위치도 카운팅에 포함한다.

 

 

대표적인 탐색알고리즘은 DFS와 BFS를 동시에 살펴본다. DFS는 루트노드에서 단말노드까지 한번에 진입하여 탐색하는 스택 기반 알고리즘이다. 즉 최단거리를 구하는 알고리즘으로 적합하지 않다. DFS로 탐색을 시도하면 가능한 모든 경로를 탐색하기 때문에 최단거리가 나오지 않는다.

 

BFS 알고리즘을 사용해서 문제를 풀기 위해서는 탐색된 노드의 순서를 기록하는 2차 배열이 필요하다. 완전탐색에서 방문하지 않은 좌표값이면서, 숫자가 1인 노드의 숫자를 계산하면서 마지막 노드의 좌표값을 구하게 되면 최단거리가 계산된다. 아래 결과값을 보면 (3,4) 좌표에서 경우의 수가 3개가 존재하지만 마지막 좌표까지 도달하는데 걸린 숫자는 9가 출력된다.

 

<<입력값>>
110110
110110
111111
111101

<<노드 탐색 순서>>
1 2 0 8 9 0 
2 3 0 7 8 0 
3 4 5 6 7 8 
4 5 6 7 0 9

 

 

 

DFS/BFS 알고리즘 참고

 

백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘 리뷰

 

백준 2667 자바 JAVA 단지 번호 붙이기 알고리즘

 

백준 1260 DFS와 BFS 알고리즘 자바 JAVA

 

 

 

 

백준 2178 자바 DFS 알고리즘 CODE

 

/*
    Owner : Developer Blog
    Title : 미로 탐색
    Algorithm : DFS 알고리즘
    Date : 2022-03-08
*/

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.awt.Point;

public class A_2178 {
    private static int N,M;
    private static char[][] matrix;
    private static boolean[][] visit;
    private static Queue<Point> queue;
    private static int[] NEW_X = {-1,1,0,0};
    private static int[] NEW_Y = {0,0,-1,1};
    private static int[][] distance;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        matrix = new char[100][100];
        visit = new boolean[100][100];
        distance= new int[100][100];

        for(int i=0; i<N; i++){
            String str = in.next();
            for(int j=0; j<M; j++){
                matrix[i][j] = (char) (str.charAt(j));
            }
        }
        
        distance[0][0]=1;
        dfs(0,0);
        System.out.println(distance[N-1][M-1]);  
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                System.out.print(distance[i][j]+" ");
            }
            System.out.println();
        }
    }
   
    private static void dfs(int x, int y){
        visit[y][x] = true;
        

        for(int i=0; i<4; i++){
            int new_x = x+NEW_X[i];
            int new_y = y+NEW_Y[i];
            if(new_x>=0 && new_y>=0 && new_x<M && new_y<N  ){
                if(matrix[new_y][new_x]=='1' && !visit[new_y][new_x]){
                    distance[new_y][new_x]=distance[y][x]+1;
                    dfs(new_x,new_y);
                    visit[y][x] = true;
                }
            }
            
        }
    }
}

입력값

4 6
110110
110110
111111
111101

결과값

아래 결과는 탐색경로의 순서를 나타낸 값이다. 한 노드의 연결된 자식노드들을 검색하는 것이 아니라, 가능한 모든 경우의 수를 탐색하기 때문에 최단거리가 나오지 않는다. 면적을 계산하는 문제나, 군집의 갯수를 파악하는 문제는 DFS 알고리즘 성능이 좀더 좋게 나오지만 최단 거리 탐색 문제는 BFS 알고리즘으로 풀어야 한다.

1    2     0    12    13    0 
4    3     0    11    10    0 
5    6     7    8     9    10 
12   11   10    9     0    11

 

 

 

백준 2178 자바 BFS 알고리즘 CODE

/*
    Owner : Developer Blog
    Title : 미로 탐색
    Algorithm : BFS 알고리즘
    Date : 2022-03-08
*/


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.awt.Point;

public class A_2178 {
    private static int N,M;
    private static char[][] matrix;
    private static boolean[][] visit;
    private static Queue<Point> queue;
    private static int[] NEW_X = {-1,1,0,0};
    private static int[] NEW_Y = {0,0,-1,1};
    private static int[][] distance;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        matrix = new char[100][100];
        visit = new boolean[100][100];
        distance= new int[100][100];

        for(int i=0; i<N; i++){
            String str = in.next();
            for(int j=0; j<M; j++){
                matrix[i][j] = (char) (str.charAt(j));
            }
        }
        
        bfs(0,0);
        System.out.println(distance[N-1][M-1]);  
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                System.out.print(distance[i][j]+" ");
            }
            System.out.println();
        }
    }
    private static void bfs(int x, int y){
        visit[y][x] = true;
        distance[y][x]=1;
        queue = new LinkedList<>();
        queue.add(new Point(x,y));

        while(!queue.isEmpty()){
            Point temp = queue.poll();

            if(temp.x == M && temp.y==N){
                count++;
                break;
            } 

            
            for(int i=0; i<4; i++){
                int new_x = temp.x+NEW_X[i];
                int new_y = temp.y+NEW_Y[i];
                if(new_x>=0 && new_y>=0 && new_x<M && new_y<N  ){
                    if(matrix[new_y][new_x]=='1' && !visit[new_y][new_x]){
                        distance[new_y][new_x]=distance[temp.y][temp.x]+1;
                        queue.add(new Point(new_x, new_y));
                        visit[new_y][new_x] = true;
                    }
                }                
            } 
        }
    }
}

입력값

4 6
110110
110110
111111
111101

출력값

BFS 알고리즘은 특정 노드에 연결된 자식 노드들을 큐 자료구조로 넣어서 완전 탐색을 진행하기 때문에 최단거리를 구하는 문제에서는 최적화된 알고리즘이다. 아래 결과값을 보면 (0,0)에서 한칸씩 이동할 때 마다 탐색 순서를 기록하고 있다. 여러 방향의 노드들을 만났을 때, 완전탐색을 진행하기 때문에 마지막 좌표까지 최단 거리를 구할 수 있다.

9
1 2 0 8 9 0 
2 3 0 7 8 0 
3 4 5 6 7 8 
4 5 6 7 0 9

 

 

제출결과

메모리 사용 19MB 소요되었고, 시간은 252ms가 소요되었다.