알고리즘 :: 알고스팟 :: DFS :: DICTIONARY (고대어 사전)

Embedded June·2020년 7월 24일
0

알고리즘::종만북

목록 보기
3/5

문제


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

문제접근

종만북 DFS 파트의 난도 '하'로 제시된 문제이나 아직 DFS와 위상정렬(topological sort)에 대해 익숙하지 않아서 상당히 어렵게 느껴진 문제였다.

이 문제는 각 알파벳을 정점으로 표현하고, 한 알파벳이 다른 알파벳 앞에 와야 할 때 두 정점을 방향 간선으로 연결해서 DFS로 풀이하는 것이 적절하다. 문제는 다음과 같은 네 가지 과정을 거친다.

  • 주어진 N개 문자열에 대해 26가지 알파벳으로 DFS를 수행한다.
  • DFS가 종료되는 순서를 기록한다.
  • 이 순서를 뒤집으면 위상정렬 결과를 얻을 수 있다.
  • 만일, 얻은 결과에 사이클이 존재하면, 해당 결과는 DAG가 아니므로 올바른 위상정렬 결과가 아니다. 올바른 위성정렬이라면 반드시 시작 정점부터 종료 정점까지 좌측에서 우측으로 향하는 간선만 존재해야 하기 때문이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

static constexpr int ALPHABET = 26;
static vector<vector<bool>> adj(ALPHABET, vector<bool>(ALPHABET, false));
static vector<bool> visited(ALPHABET, false);
static vector<int> order;
static int C = 0, N = 0;

void makeGraph(const vector<string>& words) {
    for (int i = 1, j = 0; i < N; ++i, ++j) {
        int len = min(words[i].length(), words[j].length());
        for (int k = 0; k < len; ++k) {
            if (words[i][k] != words[j][k]) {
                // j에서 i로 향하는 간선을 만든다. (j가 i보다 앞선다.)
                adj[words[j][k] - 'a'][words[i][k] - 'a'] = true;
                break;
            }
        }
    }
}
void dfs(int here) {
    visited[here] = true;
    for (int there = 0; there < ALPHABET; ++there)
        if (adj[here][there] && !visited[there]) dfs(there);
    order.push_back(here);          // 과정 2) DFS가 종료되는 지점을 기록한다
}
vector<int> topologicalSort() {
    for (int i = 0; i < ALPHABET; ++i) 
        if (!visited[i]) dfs(i);        // 과정 1) DFS를 수행한다.
    
    reverse(begin(order), end(order));  // 과정 3) 결과를 역순으로 뒤집어 위상 정렬한다.

    for (int i = 0; i < ALPHABET; ++i)
        for (int j = i + 1; j < ALPHABET; ++j)
            if (adj[order[j]][order[i]])    // 과정 4) 오른쪽에서 왼쪽으로 가는 간선이 있다면
                return vector<int>();       // 사이클이 생성되므로 그건 거른다.
    return order;
}
void clearForLoop() {
    adj = vector<vector<bool>> (ALPHABET, vector<bool>(ALPHABET, false));
    visited = vector<bool> (ALPHABET, false);
    order.clear();
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> C;
    while (C--) {
        cin >> N;
        
        vector<string> words(N);
        for (int i = 0; i < N; ++i) cin >> words[i];

        clearForLoop();
        makeGraph(words);
        order = topologicalSort();

        if (!order.empty()) {
            for (int i = 0; i < ALPHABET; ++i) {
                char c = order[i] + 'a';
                cout << c;
            }
        }
        else cout << "INVALID HYPOTHESIS";
        cout << '\n';
    }
}
  • clearForLoop() 함수는 매 루프마다 초기화된 환경에서 진행할 수 있도록 따로 만든 모듈이다.
  • makeGraph() 함수는 입력받은 인접한 두 문자열끼리 비교해서 알파벳 문자를 간선으로 표현하는 함수다. 만일 j번째 문자가 i 번째 문자보다 앞선다면 간선을 생성한다.
  • topologicalSort() 함수는 모든 알파벳 정점을 한 번씩 시작 정점으로 삼아서 DFS를 수행하는 함수다. order 배열을 뒤집어서 원하는 결과를 만든 뒤 DAG인지 검사해서 결과를 반환한다.

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글