BOJ 1261번 알고스팟

BOJ : https://www.acmicpc.net/problem/1261

github : https://github.com/junho0956/Algorithm/blob/master/1261/1261/%EC%86%8C%EC%8A%A4.cpp

 

제대로 확인은 해보지 않았지만 

평범한 BFS로 문제를 해결하려하면 모든 범위를 다 확인해야되기 때문에 TLE 에 해당하게 될 것입니다.

(1.1) 에서 (N,M) 으로 최대한 시간내에 갈 수 있는 '최단거리' 를 어떻게 찾아야 할까요?

 

방법은 다익스트라 알고리즘 입니다.

다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 '최단거리' 를 구하는 알고리즘입니다.

 

헷갈리면 안되는 것은

크루스칼이나 프림과는 다르다는 것입니다.

구별하자면 크루스칼 == 프림 != 다익스트라 입니다.

 

크루스칼과 프림은 모든 정점을 서로 이으면서 그 구간이 최단거리가 되는 '도로망' 같은 것을 예를 들 수 있고

다익스트라는 한 정점에서 다른 정점으로의 최단거리 이기 때문에 '네비게이션' 같은 것을 예로 들 수 있겠습니다.

 

이 문제를 해결하기 위해서 사용할 수 있는 방법은 위에서 말한 크루스칼,

그리고 가장 비슷한 방법인 deque 를 이용한 BFS 가 있습니다.

deque 를 이용한 BFS 가 좀더 간편하고 쉬워서 이를 이용해서 문제를 해결하였습니다.

 

deque 를 이용한 BFS 의 가장 큰 특징은 가중치가 0일때 push_front 가중치가 1일때 push_back 한다는 것입니다.

deque 를 이용한 BFS 역시 다익스트라와 거의 유사하게 우선순위큐를 사용하듯이 가중치가 작은 정점을

먼저 사용할 수 있습니다.

 

#include <cstdio>
#include <deque>
using namespace std;
#pragma warning(disable:4996)
 
deque<pair<pair<int, int>, int> > dq;
int N, M;
int arr[100][100];
bool visit[100][100];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
 
int main() {
    scanf("%d%d", &M, &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%1d", &arr[i][j]);
 
    dq.push_back({ {0,0},0 });
    while (!dq.empty()) {
        int y = dq.front().first.first;
        int x = dq.front().first.second;
        int cnt = dq.front().second;
        dq.pop_front();
 
        if (visit[y][x]) continue;
        visit[y][x] = true;
 
        if (y == N - 1 && x == M - 1) {
            printf("%d", cnt);
            break;
        }
 
        for (int i = 0; i < 4; i++) {
            int yy = y + my[i];
            int xx = x + mx[i];
            if (yy >= 0 && xx >= 0 && yy < N && xx < M && !visit[yy][xx]) {
                if (arr[yy][xx]) dq.push_back({ {yy,xx},cnt + 1 });
                else dq.push_front({ {yy,xx},cnt });
            }
        }
    }
 
    return 0;
}