[알고스팟] DICTIONARY - 고대어 사전 (C++, 위상 정렬)

문제

https://algospot.com/judge/problem/read/DICTIONARY

algospot.com :: DICTIONARY

 

 

풀이

종만북 난이도: 하

 

책에서는 쉬운 난이도로 분류되었지만 사실 위상 정렬(topological-sort) 자체는 난이도 있는 알고리즘이라 생각한다.

특히 책에서는 간단히 DFS방식의 위상 정렬을 다루었지만 큐를 사용한 위상 정렬 방식이 좀 더 자주 사용되는 듯하니 둘 다 알아 두자.

 

일단 이번 문제는 DFS방식의 위상 정렬로 해결해보자.

입력은  사전 순으로 주어지므로 현재의 단어 idx로는 다음 단어 idx+1과만 비교해도 충분하다.

예를 들어 아래 세 단어를 생각해보자.

1. lox

2. loz

3. loy

1번과 2번은 lo까지는 같지만 x와 z가 다르기 때문에 x 다음이 z라는 정보를 얻을 수 있다.

1번과 3번을 비교하면 x 다음이 y 라는 사실을 알 수 있지만

1번의 다음 사전 순인 2번과 3번을 비교해도 z 다음이 y임을 알 수 있고 x 다음이 z이기 때문에

x-> z -> y의 순서임을 충분히 알아낼 수 있다.

 

따라서 alphabet_connection[i][j]에 i 다음이 j라는 정보를 다음과 같이 저장해 두자.

 

string temp;
for(int i = 0; i<word_num ; ++i){
  cin>>temp;
  dictionary.push_back(temp); 
}
 
int min_len;
for(int idx=0; idx<word_num-1 ; ++idx){
  min_len = min(dictionary[idx].size() , dictionary[idx+1].size());
  for(int len =0; len<min_len ;++len){
      if(dictionary[idx][len] != dictionary[idx+1][len]){
        alphabet_connection[dictionary[idx][len] - 'a'][dictionary[idx+1][len] - 'a'] = true;
        break;
      }
  }
}

 

alphabet_connection을 통해 이제 그래프를 방문할 수 있다.

DFS방식의 위상 정렬에서는 DFS방식의 그래프 순회를 통해 종료되는 순서를 저장한다.

 

void TopologyDFS(int idx){
  visited[idx] = true;
 
  for(int i =0; i<26 ; ++i){
    if(alphabet_connection[idx][i] && !visited[i]){
      TopologyDFS(i);
    }
  }
  alphabet_order.push_back(idx);
}

 

이때 방문한 노드는 더 이상 방문할 필요가 없으므로 visited 표시를 해주자.

(재방문 시 종료 순서에 중복되어 삽입되게 됨.)

 

 

단, 문제에서 위상 정렬을 하기 위해서는 그래프들이 사이클이 존재하지 않는 DAG(Directed Acycle Graph)인지 확인해야 한다.

즉, 사전 순에 모순이 있는지 확인해야 한다.

 

다음과 같은 사전 순을 그래프로 표현해보면 사이클(사전 순의 모순)이 생긴다.

 

1. ab

2. ac

3. bc

4. ba

만약 TopologyDFS(a)가 먼저 호출되었다면

방문된 알파벳은 alphabet_order에 a, b, c 순서대로 저장되어있을 것이다.

따라서 그래프의 방문이 끝난 후, 역순을 가리키는 그래프가 있는지 직접 확인해주자.

 

for(int i=0; i<alphabet_order.size() ; ++i ){
  for(int j= i+1; j<alphabet_order.size() ; ++j){
    if(alphabet_connection[alphabet_order[i]][alphabet_order[j]]){  //역순이 존재해 DAG가 아닌 경우
      cout<<"INVALID HYPOTHESIS\n";
      is_possible = false;
      break;
    }
  }
  if(!is_possible)
    break;
}

 

최종적으로는 역순으로 저장된 방문 순서를 뒤집어서 출력해주면 된다.

 

(같은 문제인줄 알고 풀려다 된통 당한 문제의 링크도 올려봅니다.)

[백준] 알고스팟어(2848)

 

코드