백준 2178번 [미로 탐색](C++) -yes6686- 티스토리

백준 문제 풀이: 2178 [미로 탐색]

---

문제 링크: https://www.acmicpc.net/problem/2178

문제 설명:

n × m 크기의 미로에서 (1,1)에서 (n,m)으로 이동하려고 합니다. 이동할 수 있는 경로는 1로 표시된 칸이며, 상하좌우로 이동할 수 있습니다. 최단 경로의 길이를 출력하는 프로그램을 작성하세요.

입력 조건:

• 첫째 줄에 n과 m이 주어집니다. (2 ≤ n, m ≤ 100)
• 다음 n개의 줄에는 m개의 숫자로 미로가 주어집니다. (1은 이동 가능, 0은 이동 불가)

출력 조건:

• 첫째 줄에 최단 경로의 길이를 출력합니다.

---

문제 해결 코드

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

int n, m;
int arr[101][101];
int visited[101][101];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;

    while (!q.empty()) {
        int currX = q.front().first;
        int currY = q.front().second;
        q.pop();

        // 목표 지점 도달 시 거리 반환
        if (currX == n && currY == m) {
            return visited[currX][currY];
        }

        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int nextX = currX + dx[i];
            int nextY = currY + dy[i];

            // 미로 범위 내이고 이동 가능하며 방문하지 않은 경우
            if (nextX > 0 && nextX <= n && nextY > 0 && nextY <= m && arr[nextX][nextY] == 1 && visited[nextX][nextY] == 0) {
                visited[nextX][nextY] = visited[currX][currY] + 1;
                q.push({nextX, nextY});
            }
        }
    }

    return -1; // 도달 불가
}

int main() {
    cin >> n >> m;
    string row;

    for (int i = 1; i <= n; i++) {
        cin >> row;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = row[j - 1] - '0';
        }
    }

    cout << bfs(1, 1) << '\n';
    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 BFS를 사용하여 미로의 최단 경로를 계산합니다.

• 입력 처리:
  • 미로를 `arr` 배열에 저장합니다. 1은 이동 가능, 0은 이동 불가를 의미합니다.
• BFS 탐색:
  • 큐를 사용하여 BFS를 수행합니다.
  • 현재 위치에서 상하좌우로 이동 가능한 칸을 탐색하고 방문합니다.
  • 목표 위치 `(n, m)`에 도달하면 현재까지의 거리를 반환합니다.

시간 복잡도 분석:

• BFS는 모든 칸을 한 번씩 방문하므로 O(n × m).

최대 크기가 100 × 100이므로 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
4 6
101111
101010
101011
111011

출력:
15

주어진 미로에서 최단 경로의 길이를 정확히 계산하여 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!