[알고스팟/c++] 고대어 사전 DICTIONARY 문제 풀이

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

algospot.com :: DICTIONARY

접근 방식

---

1. 이 문제에서는 의존성이 있는 입력이 주어지며, 우리가 해결해야할 문제는 의존성이 있는 알파벳을 "순서대로" 출력하는 것이다. "알고리즘 문제해결전략" 책의 표현을 빌리자면, "위상 정렬은 의존성이 있는 작업들이 주어질 때, 이들을 어떤 순서로 수행해야 하는지 계산해 주는 것"이다. 알파벳에 특정한 순서를 부여해 단어들을 정렬하고 있다. 이로써 위상 정렬 문제임을 알 수 있다.

 

2. 책에는 위상 정렬을 구현하는 방법으로 "깊이 우선 탐색"(DFS)을 제시하고 있다. dfs를 모든 정점에 대해 수행하면서, dfs()가 종료될 때마다 종료 시점의 정점의 번호를 순서대로 저장한 뒤, 모든 정점에 대해 탐색이 끝났다면 저장한 번호들을 뒤집으면 위상 정렬의 결과를 얻을 수 있다. (벡터 자료구조에 하나씩 push_back() 해서 저장한 뒤에, reverse() 메소드를 통해 이들의 순서를 뒤집으면 된다.)

 

고대어 사전 문제를 보기 전에, 위상 정렬과 위상 정렬 구현 방법에 대한 내용을 미리 읽었어서 책과 동일한 풀이를 떠올릴 수 밖에 없었다. (위상 정렬은 들어본 적은 있었으나, 실제로 어떤 방식으로 구현하는지 몰랐어서, 아마 이 내용을 사전에 읽지 않았다면 문제를 풀지 못 했을 것이다...)

 

3. 여기서부터는 내 시행착오?가 약간 포함되어 있다. 일단 가장 먼저 든 의문은 "단어 비교를 인접한 단어끼리만 해도 될까?" 아니면, "한 칸 이상 간격을 둔 단어끼리도 비교해야 할까?" 였다. 결국 정답은 전자가 YES 였다.

 

근거는 바로 방향 그래프의 transitive 한 속성에 있다. 

 

간단하게 설명하자면, "a 정점에서 b 정점으로 갈 수 있고, b 정점에서 c 정점으로 갈 수 있으면, a 정점에서 c 정점으로 갈 수 있다." 이러한 속성을 말한다.

 

* 애초에 단어는 순서대로 주어졌고, 뒤에 입력된 단어일수록 순서가 밀린다는 것을 그대로 받아들이면 된다. 앞에 입력된 단어가 뒤에 입력된 단어보다 순서에서 앞서기 때문에, 인접한 단어끼리만 비교해도 된다. 왜냐하면 두 번 뒤에서 입력된 단어보다도 순서에서 앞서는게 보장되기 때문이다.

 

4. 두 번째로 든 의문은 위상 정렬 결과가 올바른지 확인하기 위해서 역행 간선이 있는지 체크를 어떻게 할지에 대한 것이었다. 즉, 싸이클이 존재하는지 확인하는 방법에 대한 고민을 했다. 이 고민도 두 가지 사이에서 갈등했다. "인접한 정점 사이에 역행하는 간선이 있는지만 체크하면 될까?" 아니면 "두 다리를 넘어서 다시 돌아왔을 때에 대해서 체크하기 위해 dfs를 각 정점에 대해 돌아야 할까?" 였다. 정답은 전자가 YES 였다.

 

지금와서 생각해보면 이 고민을 왜 했을까 싶을 정도로 너무 간단했다.

 

어차피 모든 인접하는 정점 쌍들에 대해서 역행하는 간선이 있는지 체크할 것인데, 몇 다리를 건너서 싸이클이 형성되어 있는지 체크할 필요가 전혀 없었다. 애초에 싸이클이 생기려면, 하나의 간선은 역행해야 하는 것이고, 모든 인접하는 정점 쌍들에 대해서 체크할 것이니까 굳이 방향 그래프에서 싸이클이 존재하는지 체크하기 위한 dfs를 돌릴 필요 자체가 없다. 

 

예를 들어, a -> b -> c -> a 라는 싸이클이 있다고 하자. 그러면, 어차피 c 에서 a 로 역행하는 간선이 있기 때문에, 애초에 a에서 dfs를 돌아서 다시 돌아오는지 확인할 필요가 없는 것이다. c -> a 를 체크할 때 이미 a -> c 라는 간선이 그래프 정보에 있기 때문에 이 간선이 역행하는 간선인지 바로 확인할 수 있기 때문이다.

 

그렇게 해서 간단한 풀이는 이러하다.

인접한 두 단어에 대해 각 알파벳을 단어의 맨 앞부터 비교한다. 만약 두 알파벳이 다르다면, 앞 단어의 알파벳에서 그 다음 단어의 알파벳을 잇는 간선을 추가한다. (알파벳을 정점으로 생각한 것이다. 그래프에 저장하기 쉽게 각 알파벳에 대해 - 97을 해서 정수값으로 변환한 뒤에 그래프 정보를 초기화하자.) 그리고 각 알파벳에 대해서 만약 방문되지 않았다면, dfs를 하고, dfs가 종료되는 시점에서의 정점을 order 라는 벡터에 하나씩 추가하자. 이를 reverse를 통해 순서를 뒤집은 뒤에, 역행하는 간선이 있는지 모든 인접한 두 정점에 대해 체크하자. ( a -> b , b -> a 가 있으면 a -> b 일 때만 체크하면 된다. 대칭하는지 체크하는 것이기 때문에, 정확히는 반만 체크하면 된다.)

 

정답 코드

---

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 5e5;

int T, N;
int graph[26][26];
bool visited[26];
vector <int> order;
void dfs(int here){
  visited[here] = true;
  for(int i = 0; i < 26; i++){
    if(graph[here][i] && !visited[i])
      dfs(i);
  }
  order.push_back(here);
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> T;
  while(T--){
    cin >> N;
    vector <string> st;
    for(int i = 0; i < N; i++){
      string s;
      cin >> s;
      st.push_back(s);
    }
    bool validity = true;
    for(int i = 0; i < N - 1 ; i++){
      int j = i + 1;
      int len = min(st[i].size(),st[j].size());
      for(int k = 0; k < len; k++){
        if(st[i][k] != st[j][k]){
          int xInt = st[i][k] - 'a', yInt = st[j][k] - 'a';
          graph[xInt][yInt] = 1;
          break;
        }
      }
    }
    for(int i = 0; i < 26; i++){
        if(!visited[i])
          dfs(i);
    }
    reverse(order.begin(),order.end());
    for(int i = 0; i < 26 ; i++){
      for(int j = i + 1; j < 26; j++){
        if(graph[order[j]][order[i]]){
          validity = false;
          break;
        }
      }
      if(!validity)
        break;
    }
    if(validity){
      for(int i = 0; i < order.size(); i++){
        cout << char(order[i]+97);
      }
    }
    else{
      cout << "INVALID HYPOTHESIS";
    }
    cout << '\n';
    for(int i = 0; i < 26; i++){
      visited[i] = false;
      for(int j = 0; j < 26; j++){
        graph[i][j] = 0;
      }
    }
    order.clear();
  }
	return 0;
}

배운점

---

1. 위상 정렬, 위상 정렬 구현 방법(DFS)

2. 그래프 정보를 초기화할 때, 재귀함수를 사용해서 했으나, for 문으로도 간단히 작성될 수 있는 것이었다. 재귀함수를 사용해서 그래프 정보를 초기화한 코드는 시간 초과가 뜬다! 재귀함수가 for 문보다 느리다는 것은 알고 있었는데, 이정도일줄은.. 몰랐다. 간단한 초기화를 위한 용도거나 코드 가독성에 있어 그리 크게 차이가 나지 않는다면, for 문을 쓰자. 

 

비교를 위해 재귀함수로 작성한 그래프 초기화 코드를 같이 올려야 겠다.

void init(string x, string y, int idx){ 
  if(idx >= x.size() || idx >= y.size())
    return;
  if(x[idx] == y[idx])
    init(x,y,idx+1);
  else{
    int xInt = x[idx] - 'a', yInt = y[idx] - 'a';
    graph[xInt][yInt] = 1;
    return;
  }
  
  // 재귀함수로 초기화했더니 시간 초과가 발생했다.