백준 - 2665 미로 만들기

 

해결과정 - bfs, 우선순위 큐

처음 해결 방법은 그래프 형식으로 바꾼다음 다익스트라 알고리즘이나 플로이드 워셜 알고리즘을 사용하는 것이였다. 하지만 거리의 개념으로 변환시키는것 자체가 이 문제였기에 기각하였다.

 

그래서 해결방법의 아이디어를 다익스트라 알고리즘에서 착안하였다 갈수 있는공간의 비용은 0으로 벽은 비용을 1로 취급한다음 이를 이용하여 bfs로 탐색하면서 중복되는 방 탐색없이 n^2 * longn 시간복잡도 안에 이 문제를 해결할 수 있었다

 

#include <bits/stdc++.h>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int check[50][50];
int board[50][50];
int n;

struct Node {
    int value, x, y;
    Node(int value, int x, int y) : value(value), x(x), y(y) {}

    bool operator<(const Node& node) const {
        return value > node.value;
    }
};
void solve() {
    priority_queue<Node> pq;
    pq.push(Node(0, 0, 0));

    while (!pq.empty()) {
        int curX = pq.top().x;
        int curY = pq.top().y;
        int curValue = pq.top().value;
        pq.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = curX + dir[i][0];
            int nextY = curY + dir[i][1];

            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) continue;
            if (check[nextX][nextY] == -1) {
                check[nextX][nextY] = curValue + board[nextX][nextY];
                pq.push(Node(check[nextX][nextY], nextX, nextY));
            }
            
        }
    }
}

int main() {
    FAST;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < n; j++) {
            int num = str[j] - '0';
            board[i][j] = abs(num - 1);
		}
	}
    memset(check, -1, sizeof(check));
    solve();
    cout << check[n - 1][n - 1] << '\n';
    return 0;
}

 

후기

다른 사람 코드를 보니 1단계에 갈수 있는곳 2단계에 갈수있는곳 이런식으로 차근차근 업데이트하여 해결하는 코드가 있는데 시간은 조금더 오래걸리겠지만 메모리 측면에서는 아주 효율적인것 같다.