백준 2178번 - 미로탐색

 

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

2178번: 미로 탐색

가장 대표적인 미로탐색 문제의 정석이라고 할 수 있다.

 

보통 이러한 미로탐색류의 문제들은 BFS(Breadth-First Search) 알고리즘을 사용해서 

 

문제를 해결하는 것이 보통이다.

 

어떤 식의 로직이 들어가는지 아래에서 살펴보자.

 

위와 같은 미로가 있을 때, 1행 1열부터 마지막행 마지막열까지

 

최소 몇번을 이동하는지 카운트하는 문제이다.

 

최소 경로는 아래의 경로와 같다. 

 

그럼 위의 로직을 어떤 식으로 구현해야 할지 살펴보자.

 

일단 아래와 같이 방문배열을 하나 만들어준다.

1) 1행 1열부터 bfs 알고리즘을 적용해 준다. 또한, 방문배열 첫 번째 영역의 값을 1로 지정해 준다.

2) 상하좌우의 값을 확인해 준다 배열을 넘어가는 인덱스인 경우에는 무시해 준다.

3) 0일 경우에는 벽이므로 갈 수 없는 영역이고 1일 때만 나아갈 수 있는 영역이다.

4) bfs를 통해서 다음영역을 지정해서 갈 경우에 해당영역의 값을 전 영역의 방문배열값 + 1로 지정해 준다.

5) 위의 로직을 계속 반복해 주고, 커서가 마지막행 마지막열에 도착할 때 계산을 끝내고 답을 도출해 준다.

 

그럼 방문배열의 값은 아래와 같아질 것이다.

 

즉 가장 최소로 미로를 빠져나갈 수 있는 영역의 개수는 15칸이 된다.

 

그럼 여기서 의문이 하나 들 수 있다.

 

왜 미로탐색 알고리즘은 DFS(Depth-First Search)를 사용하여 해결하기 힘든 것일까?

 

일단 아래와 같은 CASE를 생각해 보자.

 

일단 위의 미로를 기반으로 BFS(Breadth-First Search) 알고리즘 적용하여 도식화해보자.

 

BFS는 방문배열과 Queue를 사용하여 구현한다.

 

(1,1)을 Queue에서 뽑은 다음,  상하좌우로 인접한 칸을 Queue 에 다시 넣어준다.

 

 

위와 같은 논리대로 마지막 배열까지 가보면 아래와 같다.

 

진한빨간색 칸은 해당 칸으로 오기까지 해당 칸을 포함해서 몇 개의 칸을 넘어왔는지

 

적어주는 칸이라고 생각하면 된다.

 

 

위의 그림에서 보는 것과 같이

 

(1,1)에서 (4,6)까지 도달하는 가장 최소의 거리는 9 임을 알 수 있다.

 

하지만, 해당 문제를 DFS로 풀었을 경우에는 최솟값이 9가 나오지 않을 수 있다.

 

일반적으로 DFS 알고리즘은 재귀함수를 이용하거나,

 

Stack 자료구조를 사용한다.

 

 

아래와 같이 (1,1) 배열에 도착했을 경우에는 아래와 같은 형식이 된다.

 

DFS는 BFS 와는 다르게 Stack을 사용하거나

 

재귀함수를 사용하여 Call stack에 함수를 쌓고, 꺼내는 방식을 사용한다.

 

물론, 운이 좋게 가장 최단경로를 DFS를 사용해서 찾을 수 도 있지만,

 

아래와 같은 최악의 경우가 발생할 수 있다.

 

 

물론 가중치를 주거나 DFS 를 변형하여 올바른 정답을 끌어낼 수 있다.

 

하지만 시간복잡도가 매우 커지게 되는 문제가 발생한다.

 

그러므로, 미로탐색과 같은 알고리즘 문제를 해결하려고 할 때에는

 

DFS 알고리즘이 아닌 BFS 알고리즘을 선택하는 게 올바른 방법이다.

 

 

아래에는 각 언어별로 BFS 알고리즘을 적용하여 풀이한 해법이다.

 

 

 

1. C++

 

#include <iostream>
#include <queue>
#include <utility>
#include <string>

using namespace std;

int N,M;
int maze[100][100];
bool visited[100][100];
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void bfs(int cur_r, int cur_c)
{
    queue<pair<int,int>> maze_q;
    visited[cur_r][cur_c] = true;
    maze_q.push(make_pair(cur_r, cur_c));

    while(!maze_q.empty())
    {
        int cur_r = maze_q.front().first;
        int cur_c = maze_q.front().second;
        maze_q.pop();

        if (cur_r == N-1 && cur_c == M-1) break;

        for (int i = 0; i < 4; i++)
        {
            int new_r = cur_r + dr[i];
            int new_c = cur_c + dc[i];

            if (new_r >= 0 && new_c >= 0 && new_r < N && new_c < M && maze[new_r][new_c] != 0 && !visited[new_r][new_c])
            {
                visited[new_r][new_c] = true;
                maze_q.push(make_pair(new_r, new_c));
                maze[new_r][new_c] = maze[cur_r][cur_c] + 1;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        string inputs;
        cin >> inputs;

        for (int j = 0; j < inputs.length(); j++)
        {
            maze[i][j] = inputs[j] - '0';
        }

    }

    bfs(0,0);

    cout << maze[N-1][M-1] << endl;

    return 0;
}

 

 

 

2. JAVA

package Maze2178;

import java.io.*;
import java.util.*;

public class Maze2178_1 {

    static int N,M;
    static int[][] maze;
    static boolean[][] visited;
    static int[] dr = {1,0,-1,0};
    static int[] dc = {0,1,0,-1};

    static class Pair {
        public int row;
        public int col;

        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }   

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        
        maze = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String[] inputs = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                maze[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        bfs(0,0);   

        bw.write(maze[N-1][M-1] + "");
        bw.close();
        br.close();
    }

    static void bfs(int row, int col) {
        
        visited[row][col] = true;
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(row, col));

        while (!queue.isEmpty()) {
            int curR = queue.peek().row;
            int curC = queue.peek().col;

            queue.poll();

            if (curR == N-1 && curC == M-1) break;   

            for (int i = 0; i < 4; i++) {
                int newR = curR + dr[i];
                int newC = curC + dc[i];
                
                if (newR >= 0 && newC >= 0 && newR < N && newC < M && !visited[newR][newC] && maze[newR][newC] != 0) {
                    visited[newR][newC] = true;
                    queue.add(new Pair(newR, newC));
                    maze[newR][newC] = maze[curR][curC] + 1;
                }
            }
        }
    }
}

 

 

3. Python

import sys
from queue import Queue

input = sys.stdin.readline

dr = [0,1,0,-1]
dc = [1,0,-1,0]

N, M = map(int, input().split())
maze_map = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]

def bfs(cur_r,cur_c):
    visited[cur_r][cur_c] = 1
    
    for i in range (4):
        new_r = cur_r + dr[i]
        new_c = cur_c + dc[i]

        if (new_r >= 0 and new_c >= 0 and new_r < N and new_c < M and visited[new_r][new_c] == 0 and maze_map[new_r][new_c] != 0):
            maze_queue.put([new_r, new_c])
            visited[new_r][new_c] = True
            maze_map[new_r][new_c] = maze_map[cur_r][cur_c] + 1


maze_queue = Queue()
maze_queue.put([0,0])

while(not maze_queue.empty()):
    
    cur_r, cur_c = maze_queue.get()

    if (cur_r == N-1 and cur_c == M-1):     
        print(maze_map[N-1][M-1])        

    bfs(cur_r, cur_c)