[Bellman-Ford]BOJ 3860_할로윈 묘지

문제 링크 : www.acmicpc.net/problem/3860

3860번: 할로윈 묘지

 

2차원 배열 형태의 그래프에 대한 벨만-포드 알고리즘 적용 문제이다.

문제에서 제시된 예제는 다음과 같다.

2차원 배열 형태의 예제

이러한 2차원 배열 형태의 예제를 우리에게 익숙한 일반 그래프 형태로 나타내면 아래와 같다.

그림에서 실선으로 표현된 간선들의 가중치는 모두 1이다.

따라서, 주어진 2차원 배열 Board를 그래프의 형태로 바꾸고,

변환한 그래프에 대해 벨만-포드 알고리즘을 적용하면 된다.

다만 BOJ1219_오민식의 고민 문제와는 달리,

이 문제는 음의 사이클이 발생하는 노드에 도달 가능한지 여부는 상관하지 않는다.

문제의 서술이 애매하긴 하지만 음의 사이클이 발생한다면 무조건 Never를 우선 출력한다.

 

이 풀이에서는 2차원 배열을 변환한 그래프를 1차원 배열 형태로 저장해 사용하였다. (최대 900)

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <memory.h>
 
#define INF 99999999
 
using namespace std;
typedef pair<int, int> p;
typedef pair<p, int> hole;
 
pair<int, int> dir[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
int w, h, g, e, board[900];
int dist[900];
vector<hole> holes;
bool cycle = false;
 
void bellman(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[j] == INF) continue;
            //도착 지점에서 나가는 간선을 만들지 않는다.
            if (j == n - 1) continue;
 
            int row = j / w;
            int col = j % w;
 
            //현재 좌표가 묘비라면, 이동하지 않음
            if (board[j] == -1) continue;
 
            //현재 좌표가 귀신구멍이라면, 귀신구멍을 통한 이동만 고려
            if (board[j] > 0) {
                hole temp = holes[board[j] - 1];
                int newN = temp.first.second;
                int distval = temp.second;
                if (dist[newN] > dist[j] + distval) {
                    dist[newN] = dist[j] + distval;
                    //무한루프 발생시
                    if (i == n - 1) cycle = true;
                }
                continue;
            }
 
            //일반 잔디 칸일 경우, 4방으로 이동
            for (int k = 0; k < 4; k++) {
                int newR = row + dir[k].first;
                int newC = col + dir[k].second;
                if (newR < 0 || newR >= h || newC < 0 || newC >= w) continue;
                int newN = newR * w + newC;
                int distval = 1;
 
                //묘비는 이동 불가
                if (board[newN] == -1) continue;
 
                //이어주기
                if (dist[newN] > dist[j] + distval) {
                    dist[newN] = dist[j] + distval;
                    //무한루프 발생시
                    if (i == n - 1) {
                        cycle = true;
                    }
                }
            }
        }
    }
}
 
void init() {
    int r, c, r2, c2, t;
    memset(board, 0, sizeof(board));
    holes.clear();
 
    for (int i = 0; i < w * h; i++) dist[i] = INF;
 
    cin >> g;
    for (int i = 0; i < g; i++) {
        cin >> c >> r;
        board[r * w + c] = -1;    //묘비
    }
 
    cin >> e;
    int idx = 1;
    for (int i = 0; i < e; i++) {
        cin >> c >> r >> c2 >> r2 >> t;
        board[r * w  + c] = idx++;
        holes.push_back({ {r * w + c, r2 * w + c2}, t });    //귀신구멍
    }
 
    dist[0] = 0;
    cycle = false;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    while (1) {
        cin >> w >> h;
        if (w == 0 && h == 0) break;
        init();
        int finish = w * h - 1;
        bellman(finish + 1);
 
        if(cycle) printf("Never\n");
        else {
            if (dist[finish] == INF) printf("Impossible\n");
            else printf("%d\n", dist[finish]);
        }
    }
 
    return 0;
}