백준 2665번 [미로만들기](C++) -yes6686- 티스토리

백준 문제 풀이: 2665 [미로만들기]

---

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

문제 설명:

주어진 N×N 크기의 미로에서 시작점(0, 0)에서 도착점(N-1, N-1)까지 이동하는 데 필요한 벽을 최소한으로 부수는 문제입니다.

미로는 1과 0으로 이루어진 문자열로 주어지며, 1은 빈 방, 0은 벽을 나타냅니다. 이동할 수 있는 경로를 만들기 위해 최소한으로 벽을 부숴야 합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#define INF 1e9
using namespace std;

int arr[51][51]; // 미로 정보
int dis[51][51]; // 최소 벽 부수기 횟수
int dx[4] = {1, -1, 0, 0}; // 상하좌우 이동
int dy[4] = {0, 0, 1, -1};

priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;

void dijkstra(int n) {
    // 거리 배열 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dis[i][j] = INF;
        }
    }

    // 시작점 초기화
    dis[0][0] = 0;
    pq.push({0, {0, 0}});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();

        // 상하좌우로 이동
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 미로 범위를 벗어난 경우 무시
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

            int ncost = cost + arr[nx][ny]; // 벽을 부순 횟수 추가
            if (dis[nx][ny] > ncost) {
                dis[nx][ny] = ncost;
                pq.push({ncost, {nx, ny}});
            }
        }
    }
}

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

    int n;
    cin >> n;

    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < n; j++) {
            arr[i][j] = (s[j] == '1') ? 0 : 1; // 1은 빈 방(0 비용), 0은 벽(1 비용)
        }
    }

    dijkstra(n);
    cout << dis[n - 1][n - 1] << '\n'; // 도착점까지의 최소 비용 출력

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 다익스트라 알고리즘을 사용하여 벽을 최소로 부수는 경로를 계산합니다. 벽을 부수는 횟수를 비용으로 간주하여 최소 비용을 구합니다.
• 구현 세부사항:
  • arr[i][j]: 입력 문자열에서 1은 빈 방(0 비용), 0은 벽(1 비용)으로 변환
  • dis[i][j]: (i, j)까지 도달하기 위한 최소 벽 부수기 횟수
  • 우선순위 큐를 사용하여 최소 비용을 먼저 탐색
• 시간 복잡도 분석: O(N² log N)
  • 우선순위 큐를 사용한 다익스트라 알고리즘의 시간 복잡도
  • N은 미로의 크기

---

결과

미로의 시작점에서 도착점까지 최소로 부숴야 하는 벽의 수를 정확히 계산합니다. 다익스트라 알고리즘을 활용하여 효율적으로 풀이했습니다.

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