6주차(DFS와 BFS) - [C++]백준2178 미로 탐색

09 Apr 2022 in Study on Algorithm

백준2178 미로 탐색 링크

문제

예제 입력

---

코드

#include<iostream>
#include<queue>
using namespace std;

int n, m;
char map[100][100];
bool check[100][100];

int dist[100][100]; // 거리 - bfs 
int dfs_ans = INT_MAX; // 거리 - dfs 

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

void dfs(int x, int y, int depth) {
    // 스택 이용가능 = 재귀
    // 맵 범위 벗어난 경우 
    if (x <= -1 || x >= n || y <= -1 || y >= m)  return; 

    if (x == n - 1 && y == m - 1) {
        if (depth < dfs_ans) {
            dfs_ans = depth;
        }
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (map[nx][ny] == '1' && check[nx][ny] == false) {
            check[nx][ny] = true;
            dfs(nx, ny, depth + 1);
            check[nx][ny] = false;
        }
    }
}

void bfs(int x, int y) {
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    check[x][y] = true;
    dist[x][y] = 1;

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (map[nx][ny] == '1' && check[nx][ny] == false) {
                    q.push(make_pair(nx, ny));
                    check[nx][ny] = true;
                    dist[nx][ny] = dist[x][y] + 1;
                }
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    //bfs(0, 0);
    //cout << dist[n - 1][m - 1];
    dfs(0,0,1);
    cout<<dfs_ans;
}

설명

이 문제는 미로가 주어지고 탐색을 할때 시작점에서 종료점으로 가는 최소의 칸 수를 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 Queue를 사용하여 구현했습니다. 미로의 형태를 입력 받아 시작점(0, 0)에서 종료점(n, m)까지 경로를 탐색하는데 BFS 또는 DFS를 변형하여 두 가지 경우로 구현했습니다. BFS는 너비우선 탐색으로 나선형 모습으로 최소의 칸으로 탐색하고 DFS는 깊이우선 탐색으로 특정 방향으로 나가는 모습으로 최소의 칸을 한 번에 못 구할 수도 있어 갱신하며 탐색을 합니다. 그리고 check값을 배정하는데 이것은 같은 곳을 탐색할 수 있는 것을 방지합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과