[백준 2178 : JAVA] 미로탐색 / DFS BFS 특징

개요

 

DFS

 

Stack 혹은 재귀함수(Recursion)으로 구현된다.

• 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행
• 모든 노드를 방문하는 경우에 이 방법을 사용한다.

시간 복잡도

• 인접 리스트 : O(V + E)
• 인접 행렬 : O(V^2)

BFS

 

Queue를 사용해서 구현한다.

시간 복잡도

• 인접 리스트 : O(V + E)
• 인접 행렬 : O(V^2)

BFS는 다음의 경우 효과적으로 풀이할 수 있다.

 

1. 최소 비용 문제

2. 간선의 가중치가 1인 경우

3. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.)

 

이 문제는 1번째 조건과 최단거리 조건이 만족 때문에 DFS로 풀이하면 시간초과가 나게된다...

DFS로 풀다가 삽질을 많이 한 문제이다. 

 

 

문제

 

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입력

 

풀이

 

먼저  DFS & BFS와 방문을 확인하는 배열에 현재까지의 거리를 저장한다.

 

1. 큐에 시작 노드를 add()한다.
2. 큐에서 노드를 poll()한다.
3. 꺼낸 노드 상하좌우로 이동할 수 있는지 확인한다.이동가능하면
   1. 노드를 추가한다.
   2. 추가한 노드의 이동거리 = 현재 노드의 이동거리 + 1 (isVisit배열의 값이 0인 경우는 갈 수 없는 길이다.)
4. 큐에 값이 존재하지 않을 때까지 2, 3을 반복한다.
   • (가장 먼 곳이기 때문에 따로 예외 처리를 안하여도 큐에 값이 존재하지 않을 때까지 반복하면 된다. bfs는 물의 파동처럼 점진적으로 탐색하기 때문이다.)

 

코드

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// row, col 인덱스를 저장하는 클래스
class Location{
    int row, col;
    public Location(int row, int col) {this.row = row; this.col = col;}
}

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int arr[][];
    static int isVisit[][];
    static int n, m;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n + 1][m + 1];
        isVisit = new int[n + 1][m + 1];

        // 입력 값을 배열에 초기화
        for(int i = 1; i <= n; i++){
            String input = br.readLine();
            for(int j = 1; j <= m; j++) {
                arr[i][j] = input.charAt(j - 1) - '0';
            }
        }
        bfs();
    }

    // bfs method
    public static void bfs(){
        Queue<Location> queue = new LinkedList<>();
        // 큐에 시작점을 추가한다..
        queue.add(new Location(1,1));
        // 상하좌우 칸을 표현하는데 사용할 배열
        int[] xArr = {-1, 0, 1, 0};
        int[] yArr = {0, 1, 0, -1};
        // 추가한 노드 방문처리
        isVisit[1][1] = 1;

        while(!queue.isEmpty()){
            // 큐에서 노드를 poll
            Location location = queue.poll();
            int row = location.row;
            int col = location.col;

            // 상하좌우 4방향 노드에 대한 작업
            for(int i = 0 ; i < 4; i++){
                int x = row + xArr[i];
                int y = col + yArr[i];

                if(checkLocation(x, y)){
                    // 큐에 인접 노드 추가
                    queue.add(new Location(x, y));
                    // 추가한 노드까지의 거리 = 현재 노드까지의 거리 + 1
                    isVisit[x][y] = isVisit[row][col] + 1;
                }
            }
        }
        System.out.println(isVisit[n][m]);
    }


    public static boolean checkLocation(int row, int col){
        // 노드가 범위 밖인 경우
        if(row < 1 || row > n || col < 1 || col > m) return false;
        // 이미 방문한 노드인 경우
        if(isVisit[row][col] != 0 || arr[row][col] == 0) return false;
        return true;
    }
}