[ 백준 1613 ] 역사 (C++)

백준의 역사(1613) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 먼저, 이 문제는 BFS / DFS 알고리즘으로 분류되어 있는 문제이고, BFS / DFS로도 충분히 풀 수 있는 문제이다.

   하지만 본인은 플로이드 워샬(Floyd-Warshall) 알고리즘을 통해서 풀었다.

    * 플로이드 워샬 알고리즘 ? *

      - 플로이드 워샬 알고리즘은 모든 정점들 사이의 최단경로를 구하는 알고리즘이다.

        처음 들어보면 생소한 알고리즘 일 수도 있는데, 일단 내용자체가 어렵지 않고 구현 방법도 굉장히 쉬운 편이니

        알아두면 좋다.

        플로이드 워샬 알고리즘은 시작점에서 중간점을 거쳐서 도착점까지 갈 수 있는지 없는지 혹은 갈 수 있다면

        그 최단경로는 얼마가 되는지 3중 for문을 통해서 쉽게 구할 수 있다.

        가장 바깥쪽 for문은 중간점을, 가운데 for문은 시작점을, 가장 안쪽 for문은 도착점을 의미한다.

for (int k = 1; k <= N; k++)         // 중간점
{
    for (int i = 1; i <= N; i++)    // 시작점
    {
        for (int j = 1; j <= N; j++) // 도착점
        {
            if(시작점과 도착점의 관계를 알고싶으면)
            {
                if(시작점 > 중간점 && 중간점 > 도착점) 시작점 > 도착점
                else if(시작점 < 중간점 && 중간점 < 도착점) 시작점 < 도착점
            }
        }
    }
}

     < 플로이드 워샬의 가장 일반적인 구현 방식이다. (코딩에 정답은 없다 !) >

2) 그렇다면 이 문제가 왜 플로이드 워샬 알고리즘으로 풀이가 가능한지 알아보자.

   이 문제는 역사의 순서를 맞춰야 하는 문제이다. 예를 들어서 문제를 하나 만들어서 구체적으로 이해해보자.

   "1번 사건이 2번사건보다 먼저일어났고, 2번사건이 3번사건보다 먼저 일어났다면,

    1번과 3번중 먼저 일어난 사건은 ?"

   위와 같은 문제가 있다. 물론 정답은 1번 사건이 먼저 일어난 사건이다 이다.

   위 문제를 플로이드 워샬에 맞춰서 설명해보면,

   시작점 = 1번사건 , 도착점 = 3번사건, 중간점 = 2번사건이 되는 것이다.

   따라서, 시작점과 중간점을 비교했을 때, 시작점이 먼저이고, 중간점과 도착점을 비교했을 때 중간점이 먼저이기

   때문에 시작점이 도착점을 비교하면 시작점이 먼저라고 결론을 낼 수 있다.

  

3) 본격적으로 플로이드 워샬을 통해서 구현하는 방법을 알아보자.

   입력으로 2개의 숫자를 입력 받는대, 먼저 나온 숫자가 뒤에나온 숫자보다 먼저 일어난 사건임을 뜻한다.

   본인은 이를 저장하기 위해서 2차원 MAP[][] 배열을 사용하였다.

   입력시, MAP[a][b] = -1, MAP[b][a] = 1 로 알 수 있는 사건들의 순서를 저장해 주었다.

   이후 플로이드 워샬 풀이에 바로 들어갔다. 현재 우리는 MAP[][] = 0의 사건들에 대해서만 결과를 얻어내면 된다.

   왜냐하면, 입력할 때, 이미 순서를 알 수 있는 사건들은 1과 -1로 표시를 해 두었기 때문이다.

   즉, MAP[][] = 0 이라는 의미는 사건의 순서를 알 수 없다는 의미이다.

  

   위의 플로이드 워샬 구현방식에 그대로 대입해보면...

  

for (int k = 1; k <= N; k++)
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (MAP[i][j] == 0)
            {
                if (MAP[i][k] == 1 && MAP[k][j] == 1) MAP[i][j] = 1;
                else if (MAP[i][k] == -1 && MAP[k][j] == -1) MAP[i][j] = -1;
            }
        }
    }
}

    이렇게 된다 !

[ 소스코드 ]

 

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 401
using namespace std;
 
int N, K, S;
int MAP[MAX][MAX];
vector<pair<int, int>> Want;
 
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < K; i++)
    {
        int a, b;
        cin >> a >> b;
        MAP[a][b] = -1;
        MAP[b][a] = 1;
    }
    cin >> S;
    for (int i = 0; i < S; i++)
    {
        int a, b;
        cin >> a >> b;
        Want.push_back(make_pair(a, b));
    }
}
 
void Solution()
{
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (MAP[i][j] == 0)
                {
                    if (MAP[i][k] == 1 && MAP[k][j] == 1)
                    {
                        MAP[i][j] = 1;
                    }
                    else if (MAP[i][k] == -1 && MAP[k][j] == -1)
                    {
                        MAP[i][j] = -1;
                    }
                }
            }
        }
    }
 
    for (int i = 0; i < Want.size(); i++)
    {
        int a = Want[i].first;
        int b = Want[i].second;
 
        cout << MAP[a][b] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}