[C++] 백준 2178번 미로 탐색

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

풀이

미로의 출발점부터 도착점까지의 최단 거리를 구하는 문제이므로 BFS를 적용하였다.

큐에 {현재 좌표, 이동횟수} 쌍을 저장하기 위해 큐에 저장하는 좌표는 1차원 형태로 만들었다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<vector<char>> arr;

vector<int> moves(int pos) {
    vector<int> res;
    int x = pos / M;
    int y = pos % M;

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

    for(int i=0; i<4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < N && ny >= 0 && ny < M && arr[nx][ny] == '1') {
            res.push_back(nx * M + ny);
        }
    }

    return res;
}

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

    int ans = 0;
    cin >> N >> M;

    arr.assign(N, vector<char>(M));
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> arr[i][j];
        }
        cin.ignore();
    }

    queue<pair<int, int>> q;
    vector<bool> visited(N * M);

    int dest = N * M - 1;
    q.push({0, 1});
    while(!q.empty()) {
        int pos = q.front().first;
        int cnt = q.front().second;
        q.pop();
        visited[pos] = true;

        if(pos == dest) {
            ans = cnt;
            break;
        }

        for(int next : moves(pos)) {
            if(visited[next]) continue;
            q.push({next, cnt + 1});
            visited[next] = true;
        }
    }

    cout << ans;
    return 0;
}

시간복잡도

BFS의 시간복잡도는 O(V+E) (V는 노드, E는 간선) 인데,
이 풀이에서의 V는 미로의 칸 수로 N×M, E는 각 칸이 갖는 상하좌우 4개의 간선으로 4×N×M 이므로
시간복잡도는 O(NM)이다.

개선점

• 큐에 이동횟수를 저장하지 않고, 2차원 좌표쌍을 저장한다. 대신 dist[x][y] 배열을 만들어서 최소 칸 수를 저장하고, 방문 여부를 체크한다.

• 입력을 받을 때 2차원 char 배열에 저장하지 않고, string 배열에 한줄씩 저장한다.