algospot WORDCHAIN

문제 링크입니다: https://algospot.com/judge/problem/read/WORDCHAIN

DFS(Depth First Search) 알고리즘을 이용하여 오일러 서킷 혹은 오일러 트레일을 이용하여 풀어야하는 문제였습니다.

오일러 서킷은 그래프의 모든 간선을 정확히 한 번씩 지나면서 시작점과 끝점이 같습니다.

반면, 오일러 트레일은 오일러 서킷과 마찬가지로 그래프의 모든 간선을 정확히 한 번씩 지나지만 시작점과 끝점이 다릅니다.

추가적으로 헤밀토니안 경로는 그래프의 모든 정점을 정확히 한 번씩 지나는 경로입니다.

알고리즘은 아래와 같습니다.

1. 그래프를 생성할 때 핵심은 각 단어의 첫 글자와 마지막 글자를 정점으로 갖고 첫 글자에서 마지막 글자로 가는 간선을 단어로 잡는 것입니다.

->checkEuler() 함수를 통해 오일러 트레일러 혹은 오일러 서킷이 생성될 수 있는 환경인지 확인

2. 1번 과정을 거치면 방향 그래프가 생성되는데 해당 그래프가 오일러 서킷인지 오일러 트레일인지 혹은 모두 성립하지 않는지를 판별합니다.

3. 오일러 트레일이나 오일러 서킷이 존재한다면 방문 순서를 뒤집은 뒤 간선들을 출력해줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

using namespace std;

 

const int MAX = 30;

 

//그래프의 인접 행렬

vector<vector<int>> adj;

//graph[i][j]=i로 시작해서 j로 끝나는 단어의 목록

vector<string> graph[MAX][MAX];

//indegree[i] = i로 시작하는 단어의 수

//outdegree[i] = i로 끝나는 단어의 수

vector<int> indegree, outdegree;

 

void makeGraph(const vector<string> &words)

{

        //전역 변수 초기화

        for (int i = 0; i < MAX; i++)

                 for (int j = 0; j < MAX; j++)

                         graph[i][j].clear();

 

        adj = vector<vector<int>>(MAX, vector<int>(MAX, 0));

        indegree = outdegree = vector<int>(MAX, 0);

       

        //각 단어를 그래프에 추가

        for (int i = 0; i < words.size(); i++)

        {

                 int a = words[i][0] - 'a';

                 int b = words[i][words[i].size() - 1] - 'a';

                 graph[a][b].push_back(words[i]);

                 adj[a][b]++;

                 outdegree[a]++;

                 indegree[b]++;

        }

}

 

//directed 그래프의 인접 행렬 adj가 주어질 때 오일러 서킷 혹은 트레일 계산

void getEulerCircuit(int here, vector<int> &circuit)

{

        for (int there = 0; there < adj.size(); there++)

                 while (adj[here][there] > 0)

                 {

                         adj[here][there]--; //간선을 지운다

                         getEulerCircuit(there, circuit);

                 }

        circuit.push_back(here);

}

 

//현재 그래프의 오일러 트레일이나 서킷을 반환한다

vector<int> getEculterTrailOrCircuit(void)

{

        vector<int> circuit;

        //우선 트레일을 찾아본다: 시작점이 존재하는 경우

        for(int i=0; i<MAX; i++)

                 if (outdegree[i] == indegree[i] + 1)

                 {

                         getEulerCircuit(i, circuit);

                         return circuit;

                 }

 

        //아니면 서킷이니, 간선에 인접한 아무 정점에서나 시작

        for(int i=0; i<MAX; i++)

                 if (outdegree[i])

                 {

                         getEulerCircuit(i, circuit);

                         return circuit;

                 }

 

        //모두 실패한 경우 빈 배열 반환

        return circuit;

}

 

//현재 그래프의 오일러 서킷/트레일 존재 여부 확인

bool checkEuler(void)

{

        //예비 시작점과 끝점의 수

        int plus1 = 0, minus1 = 0;

        for (int i = 0; i < MAX; i++)

        {

                 int delta = outdegree[i] - indegree[i];

                 //모든 정점의 차수는 -1, 1, 또는 0이여야한다

                 if (delta < -1 || delta > 1)

                         return false;

                 if (delta == 1)

                         plus1++;

                 if (delta == -1)

                         minus1++;

        }

        //시작점과 끝점은 각 하나씩 있거나 하나도 없어야 한다

        return (plus1 == 1 && minus1 == 1) || (plus1 == 0 && minus1 == 0);

}

 

string solve(const vector<string> &words)

{

        makeGraph(words);

        //차수가 맞지 않으면 실패

        if (!checkEuler())

                 return "IMPOSSIBLE";

        //오일러 서킷이나 경로를 찾아낸다

        vector<int> circuit = getEculterTrailOrCircuit();

        //모든 간선을 방문하지 못했으면 실패

        if (circuit.size() != words.size() + 1)

                 return "IMPOSSIBLE";

 

        //방문 순서를 뒤집은 뒤 간선들을 모아 문자열로 만들어 반환

        reverse(circuit.begin(), circuit.end());

       

        string result;

        for (int i = 1; i < circuit.size(); i++)

        {

                 int a = circuit[i - 1], b = circuit[i];

                 if (result.size())

                         result += " ";

                 result += graph[a][b].back();

                 graph[a][b].pop_back();

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 int N;

                 cin >> N;

 

                 vector<string> words(N);

                 for (int i = 0; i < N; i++)

                         cin >> words[i];

 

                 cout << solve(words) << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]