23.08.09. 풀었던 문제들 복기

BOJ 2224. 명제 증명, 30분

 floyd warshall로 푸는 문제. floyd-warshall은 예전에 포스팅 한 적이 있다. floyd warshall의 특징은 모든 vertex에서 모든 vertex의 path weight를 최단거리로 만들고, 이를 위해 kij 순서로 for loop를 돌린다.

typedef pair<char, char> pcc;
 
////////////////////// write your code below
 
// 모든 vertex에서 모든 vertex로의 path 여부를 알아야 하므로, floyd-warshall
// directed임.
 
int V = 52;
 
int char2int(char c){
    if(isupper(c)) return c - 'A';
    if(islower(c)) return c - 'a' + 26;
}
 
char int2char(int i){
    if(0 <= i && i <= 25) return i + 'A';
    else return i + 'a' - 26;
}
 
void solve(){
	int N; cin>>N;
    vector<vector<bool>> edges(52, vector<bool>(V, false)); // edges[i][j] : i부터 j까지 path 존재
    // 0 - 25까지는 대문자, 26 - 51까지는 소문자
 
    char from, to;
    string s;
    for(int i = 0; i<N; i++){
        cin>>from>>s>>to;
        edges[char2int(from)][char2int(to)] = true;
    }
 
    for(int k = 0; k<V; k++){ // k : 중간 path
        for(int i = 0; i<V; i++){
            for(int j = 0; j<V; j++){
                if(!edges[i][j] && edges[i][k] && edges[k][j]) edges[i][j] = true;
            }
        }
    }
 
    int cnt = 0;
    vector<pcc> answers;
    for(int i = 0; i<V; i++){
        for(int j = 0; j<V; j++){
            if(i != j && edges[i][j]){
                cnt++;
                answers.push_back({int2char(i), int2char(j)});
            }
        }
    }
 
    cout<<cnt<<'\n';
    for(pcc answer : answers){
        cout<<answer.first<<" => "<<answer.second<<'\n';
    }
}

 

시간복잡도

 floyd-warshall의 시간복잡도는 vertex 개수가 V일 때 O(V$^3$). 여기서는 vertex가 최대 52개이므로 (알파벳 대/소문자) 충분히 풀 수 있다.

 

공간복잡도

 floyd-warshall의 공간복잡도는 배열을 만들기 위해 O(V$^2$)가 필요하다.