[백준] No.2848 - 알고스팟어 (C++, 위상 정렬)

문제

www.acmicpc.net/problem/2848

2848번: 알고스팟어

 

 

풀이

 

solved.ac 난이도: Platium 5

 

알고스팟의 고대어 사전(DICTIONARY) 문제와 같은 문제인 듯했지만 가능한 순서가 한 개 이상인지 판별해야 하는 문제였다.

위의 고대어 문제와 같이 DFS 위상 정렬로 해결하려다 계속 틀려서 큐를 이용한 위상 정렬로 해결하였다.

큐를 이용하는 위상 정렬 구현에 대해서는 HeeJeong Kwon님의 게시글을 참고하자.

[알고리즘] 위상 정렬(Topological Sort)이란 - HeeJeong Kwon

 

큐를 이용하는 위상 정렬에서는 해당 노드로 진입하는 간선(edge)의 개수를 저장하여 위상 정렬을 구현한다.

진입 간선의 개수를 indegree[node_idx]에 저장하고 해당 값이 0인 알파벳만 큐에 넣어준다.

 

이번 문제에서 위상정렬을 아래의 순서로 진행된다.

1. indegree가 0인 알파벳을 큐 넣어줌.

2. 큐의 front 알파벳을 꺼내 위상 정렬 순서에 저장하고, 해당 알파벳과 연결된 알파벳들의 간선을 끊어준다.

(연결된 알파벳들의 indegree에 -1을 해주는 것으로 구현.)

3. 연결을 끊은 알파벳 중 indegree가 0이 된 알파벳이 있다면 큐에 넣어준다.

4. 2와 3번을 사용한 알파벳 수만큼 반복한다.

 

indegree가 0이라는 의미는 자신의 상위 순서가 없는 알파벳임을 의미한다.

예를 들어 아래의  DAG에서는 a만이 진입 차수가 0이다.

즉, 가장 빠른 순서에 존재할 수 있다.

 

 

a만을 큐에 넣어주고 2번과 3번을 진행해주면 

a는 위상 정렬 순서에 저장된고

b와 c로의 간선이 끊기고 indegree가 0이된 b와 c가 새로 큐에 삽입된다.

 

여기서 알고스팟의 고대어 사전 문제와 차별점이 발생한다.

b와 c는 a의 다음 순서이지만 d보다는 앞에 있어야 한다.

따라서 두 가지 순서 모두 답이 될 수 있다.

1. a -> b -> c -> d

2. a-> c -> b -> d

 

이와 같이 여러 가지 순서가 발생하는 시점은 위와 같이 그래프에서 분기가 발생하는 때이다.

이때 indegree가 0인 알파벳을 저장하는 큐에 두 가지 이상의 값이 저장된다.

그러므로 queue의 size가 2 이상인 경우 "?"를 출력할 수 있도록 해주자.

 

이러한 작업을 사용한 알파벳 수(used_alphabet_num)만큼 진행하는 이유는

한 번에 큐에서 한 개의 알파벳을 pop 해 작업을 진행하기 때문에 정확히 used_alphabet_num만큼 작업을 해주면 충분하다.

 

순서가 모순되는 경우

이번에는 사전의 순서가 모순되는 경우를 생각해보자.

이때는 아래와 같이 사이클이 발생하게 된다.

 

 

이때의 indegree가 0인 알파벳은 d 뿐이므로 d에서부터 방문을 진행한다.

d와 연결된 b의 간선을 끊어 b의 indegree는 -1 => 2가 되지만 결국 어떤 노드도 indegree 0으로 변화하지 않는다.

 

 

따라서 사용한 알파벳 수(used_alphabet_num)만큼 작업을 진행하기 전에 큐가 비게 된다.

이런 경우가 바로 모순이 발생하는 시점이므로 큐가 빈다면 "!"를 출력해주자.

 

 

단! 사전의 앞 단어가 뒷 단어와 접두어는 동일하지만 더 긴 경우가 입력으로 주어진다.

ex) 

abcd

abc

 

이런 경우 바로 모순이 발생한다고 처리하여 "!"를 출력하는 예외처리를 해주지 않으면 저처럼 계속 틀립니다...

 

 

구현 코드

 

#include<iostream>
#include<string>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
 
int word_num,used_alphabet_num =0;
vector<string> dictionary;
vector<int> adj[26]; //directed edge
vector<int> alphabet_order;
bool visited[26];
int indegree[26];
 
int main(){
  cin>>word_num;
  memset(visited, false, sizeof(visited));
  memset(indegree, 0, sizeof(indegree));
 
  string temp;
  for(int i = 0; i<word_num ; ++i){
    cin>>temp;
    dictionary.push_back(temp);
    for(int j=0; j<temp.size() ; ++j){
      if(!visited[temp[j]-'a']){
        visited[temp[j]-'a'] = true;
        used_alphabet_num++;
      }
    }
  }
 
  bool is_possible = true;
  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<dictionary[idx].size() ;++len){
 
      if(len < dictionary[idx+1].size()){
        if(dictionary[idx][len] != dictionary[idx+1][len]){
          adj[dictionary[idx][len] - 'a'].push_back(dictionary[idx+1][len] - 'a');
          indegree[dictionary[idx+1][len] - 'a']++;
          break;
        }
      }else{
        is_possible = false;
        break;
      }
    }
  }  
 
  queue<int> que; //들어오는 간선(edge)이 없는 경우만 넣는 큐
  for(int i=0; i<26 ; ++i){
    if(visited[i]) //사용된 알파벳에서만
    if(indegree[i] == 0)
      que.push(i);
  }
 
  bool is_single_order = true;
  int alphabet_idx;
  for(int i =0; i<used_alphabet_num ; ++i){
    if(que.empty()){//for문을 다 돌기전에 큐가 비었다면 역방향이 있다는 것
      is_possible = false;
      break;
    }
 
    alphabet_idx = que.front();
    que.pop();
 
    if(que.size() >=1)
      is_single_order = false;  //순서가 여러개면 저장할 필요x
    else
      alphabet_order.push_back(alphabet_idx);
 
    for(int j=0; j<adj[alphabet_idx].size() ; ++j){
      if(--indegree[adj[alphabet_idx][j]] == 0)
        que.push(adj[alphabet_idx][j]);
    }
    
  }
 
  if(!is_possible){
    cout<<"!\n";
  }else if(is_single_order){
    for(int i=0; i<alphabet_order.size() ; ++i)
       cout<<(char)(alphabet_order[i]+'a');
    cout<<'\n';
  }else{
    cout<<"?\n";
  }
 
  return 0;
}

 

 

 

Git 코드