[ 백준 11562 ] 백양로 브레이크

# 문제링크

www.acmicpc.net/problem/11562

11562번: 백양로 브레이크

처음에는 하나하나 BFS로 구했다. start 에서 end 까지 queue로 돌려가면서 최적의 거리를 찾았는데, 그렇게 하면 런타임에러가 난다. 그래서 검색해보니 다들 플로이드 와샬 방법으로 풀고있었다.

 

플로이드 와샬 방법은 모든 노드에서 모든 노드로 가는 최단거리를 정리할 수 있는 방법이다. start 노드에서 end 노드를 가는데, 중간에 어떤 노드를 들러서 갔을 때 더 좋은 결과가 나오면 갱신해준다. 만약 1번 node 부터 N번 node 까지 있다고 하면, N^3 만큼 돌려봐야한다. 그래도 그게 가능한 정도라면, 이후에는 또 계산을 안해줘도 된다는 장점이 있다.

 

// 플로이드 와샬

    for (int mid = 1; mid <= n; mid++) {
        for (int start = 1; start <= n; start++) {
            for (int end = 1; end <= n; end++) {
                if (map[start][end] > map[start][mid] + map[mid][end]) {
                    map[start][end] = map[start][mid] + map[mid][end];
                }
            }
        }
    }

 

백양로 브레이커 문제도, n의 최대 크기는 250이지만, 학생들이 질문을 뭔 3만개씩 한다. 3만개 질문 들어올때마다 구하면 시간초과이지만, 최대 15,625,000‬ (250*250*250) 을 한 번만 돌리면, 이후 3만번은 그냥 O(1) 으로 초과되지 않는다..

 

플로이드 와샬을 돌리기 전에 map을 map[i][j] 가 i==j 일때는 0으로, 나머지는 큰 값으로 초기화해주어야한다. 근데 최대값을 너무 크게 (int 형에서 젤 큰 값인 0x7fffffff) 으로 줬더니 오버플로가 나는지 계산이 잘 되지 않았다. 적당히 큰 값을 넣어주어야겠다. 그러고 나서 각 map 의 weight 를 입력받으면 된다!

 

# 제출 코드 

 

#include <cstdio>
using namespace std;

int n, m; // 건물 수 , 길 수 
int map[251][251]; 
int ans;

void Input() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            map[i][j] = (i == j) ? 0 : 0x7ffff;
        }
    }

    int u, v, b;

    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &u, &v, &b);
        if (b) {
            map[u][v] = 0;
            map[v][u] = 0;
        }
        else {
            map[u][v] = 0;
            map[v][u] = 1;
        }
    }

}


void Make_All_Info() {
    for (int mid = 1; mid <= n; mid++) {
        for (int start = 1; start <= n; start++) {
            for (int end = 1; end <= n; end++) {
                if (map[start][end] > map[start][mid] + map[mid][end]) {
                    map[start][end] = map[start][mid] + map[mid][end];
                }
            }
        }
    }
}

int main() {
    Input();

    int k;
    scanf("%d", &k);

    Make_All_Info();
    int from, to;
    for (int tc = 1; tc <= k; tc++) {
        scanf("%d %d", &from, &to);
        printf("%d\n", map[from][to]);
    }
}