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

www.acmicpc.net/problem/1613

1613번: 역사

 

 

 

알고리즘 종류

    - 플로이드 와샬(floyd warshall)

 

 

 

사고 과정

    - 플로이드 와샬 적용하기

 

 

 

구현(C++)

#include <iostream>
#include <cstring>
 
using namespace std;
 
int n, k, s;
 
int mat[401][401];
 
void floyd(){
    
    for(int m=1; m<=n; m++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                
                if(mat[i][m] == mat[m][j] && mat[i][j] == 0) mat[i][j] = mat[i][m];
                
            }
        }
    }
}
 
int main(void){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    memset(mat, 0, sizeof(mat));
    
    cin >> n >> k;
    
    // 연관된 사건 입력 받기  
    int a, b;
    for(int i=0; i<k; i++){
        cin >> a >> b;
        mat[a][b] = -1;
        mat[b][a] = 1;
    }
    
    floyd();
    
    // 원하는 사건 출력  
    cin >> s;
    for(int i=0; i<s; i++){
        cin >> a >> b;
        cout << mat[a][b] << "\n";
    }
}

 

 

 

시행착오

    - 시간초과가 났다. 도저히 몰라서 다른 사람들의 풀이를 검색해 보았다. 차이를 찾으려고 다양한 방법을 수행했다. 원인은 endl 였다. endl를 쓰면 시간초과가 발생했다. "\n"를 쓰면 시간초과가 발생하지 않았다. 물론 이런 경우는 적겠지만, 속도를 조금이라도 빠르게 하기 위해서 기억해야겠다.