[BOJ알고리즘, C++]#2178_미로 탐색, 그래프, BFS, DFS

 

#1. 문제

2178번: 미로 탐색

 

---

 

#2. 풀이

 

1. 그래프 탐색

[자료구조]#6_그래프

 

그래프의 모든 정점을 탐색하기 위해 일반적으로 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)을 활용합니다. 먼저, DFS는 그래프 탐색 방법 중 하나로 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지 먼저 탐색을 수행하는 방법입니다. DFS 구현을 위해 재귀적인 방법과 스택을 활용하는 방법이 있습니다. 다음으로, BFS(너비 우선 탐색)은 그래프 탐색 방법 중 하나로 현재 정점과 인접해 있는 정점들을 먼저 탐색하는 방법입니다. BFS를 구현하는 방법은 큐 자료구조를 활용하는 방법이 있습니다. 

 

2. 꼭 기억해야 하는 미로 찾기 문제!!

 

1. dy 배열과 dx 배열을 정의합니다. 각 배열은 2차원 배열에서 x의 변화량과 y의 변화량을 의미합니다. 일반적으로, 각 칸의 동, 서, 남, 북으로 인접한 정점들을 차례대로 탐색하는 경우가 많기 때문입니다.
2. 2차원 vector 컨테이너를 선언하고, 각 칸의 값을 저장합니다.
3. BFS 수행을 위한 큐 컨테이너를 선언하고, 현재 정점과 인접한 정점들을 dy와 dx 배열을 통해 순회합니다. 이때, 인접한 정점들을 모두 순회할 수 없는 특별한 조건들이 붙어 있는 경우가 많습니다. 따라서, 조건에 합치되지 않는 인접 칸들은 탐색을 생략합니다.

 

---

 

#3. 코드

 

// 2. 정답 코드
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

typedef pair<int, int> p;

vector<string> maze;

int N, M;

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

void bfs(p start)
{
    vector<vector<int>> dist(N, vector<int>(M, -1));
    queue<p> q;

    dist[start.first][start.second] = 1;
    q.push({start.first, start.second});

    while (!q.empty())
    {
        int cy = q.front().first;
        int cx = q.front().second;

        q.pop();

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

            if (ny < 0 || ny >= N || nx < 0 || nx >= M || maze[ny][nx] == '0')
                continue;

            if (dist[ny][nx] == -1)
            {
                dist[ny][nx] = dist[cy][cx] + 1;
                q.push({ny, nx});
            }
        }
    }

    cout << dist[N - 1][M - 1];
}

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

    cin >> N >> M;

    maze.resize(N);

    for (int i = 0; i < N; ++i)
        cin >> maze[i];

    bfs({0, 0});

    return 0;
}

 

---