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$)가 필요하다.