백준 1613번 역사

문제 링크입니다: https://www.acmicpc.net/problem/1613

전형적인 플로이드-와샬 알고리즘을 사용하는 문제였습니다.

입력을 받을 때 history[일찍 발생한 사건][늦게 발생한 사건] = -1 로 초기화 하고 history[늦게 발생한 사건][일찍 발생한 사건] = 1로 초기화합니다.

그리고 플로이드-와샬 알고리즘을 적용하면 간단하게 풀리는 문제였습니다.

#include <iostream>

using namespace std;

 

const int MAX = 400 + 1;

 

int N, K;

int history[MAX][MAX];

 

//전형적인 플로이드

void floyd(void)

{

        for(int k=1; k<=N; k++)

                 for(int i=1; i<=N; i++)

                         for(int j=1; j<=N; j++)

                                 if(i==j ||j==k ||i==k)

                                          continue;

                                 else

                                          if (history[i][j] == 0)

                                          {

                                                  //i가 k보다 늦게, 그리고 k가 j보다 늦게 일어난 사건이면 i가 j보다 늦게 일어난 사건

                                                  if (history[i][k] == 1 && history[k][j] == 1)

                                                          history[i][j] = 1;

                                                  //i가 k보다 일찍, 그리고 k가 j보다 일찍 일어난 사건이면 i가 j보다 일찍 일어난 사건

                                                  else if (history[i][k] == -1 && history[k][j] == -1)

                                                          history[i][j] = -1;

                                          }

}

 

int main(void)

{

        cin >> N >> K;

 

        for (int i = 0; i < K; i++)

        {

                 int first, second;

                 cin >> first >> second;

 

                 history[first][second] = -1; //first가 second보다 일찍

                 history[second][first] = 1; //second가 first보다 늦게

        }

 

        floyd();

 

        int S;

        cin >> S;

 

        for (int i = 0; i < S; i++)

        {

                 int node1, node2;

                 cin >> node1 >> node2;

 

                 cout << history[node1][node2] << endl;

        }

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~