[Algorithm]Baekjoon 11562번 :: 백양로 브레이크

https://www.acmicpc.net/problem/11562

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
 
int n, m, k;
const int maxNum = 0x3f3f3f3f;
int adjArray[251][251];
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    memset(adjArray, 0x3f, sizeof(adjArray));
 
    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
 
        adjArray[a][a] = adjArray[b][b] = adjArray[a][b] = 0;
        adjArray[b][a] = c == 0 ? 1 : 0;
    }
 
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (adjArray[i][k] + adjArray[k][j] < adjArray[i][j])
                {
                    adjArray[i][j] = adjArray[i][k] + adjArray[k][j];
                }
            }
        }
    }
 
    cin >> k;
 
    vector<int> answers;
 
    for (int i = 0; i < k; ++i)
    {
        int s, e;
        cin >> s >> e;
 
        answers.push_back(adjArray[s][e]);
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        printf("%d\n", answers[i]);
    }
}
 
 

 

코드자체는 그냥 플로이드기본풀이같지만.. 저렇게 표현하기위해 문제를 어떻게 해석하는지가 중요하다.

 

간선정보가 주어지는데 단방향일수도, 양방향일 수도 있다.

그러다보니 특정시작지점에서 특정도착지점까지 갈 수도 있고, 못갈수도 있을 것이다.

그러면 이 때, 단방향간선을 양방향으로 바꿀 수 있다고 가정했을 때 최소 몇번을 바꿔야 도착지점에 갈수있는지 알아야하는 문제이다.

 

처음에 간선정보가 주어질 때, 1 2 0  이라면 1번지점에서 2번지점까지 단방향간선이 있다는 의미인데, 그렇기 때문에 인접배열에 기록할 때 2 1 1 로 기록해준다.

 

즉, 2번지점에서 1번지점으로 가기위해서는 단방향을 양방향으로 바꿔줘야한다는 것을 가중치 1로 표현한 것이다.

 

이걸 하나의 인접배열에 가중치로 표현했으니, 이제는 그냥 플로이드와샬로 쉽게 구할 수 있다.