[ 1 ]  [ 2 ]  [ 3 ]  [ 4 ]  [ 5 ]  [ 6 ]  [ 7 ] 
Programming Problems/Graph

끝말잇기 문제 (오일러 경로)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include "stdafx.h"
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <string>
 
using namespace std;
 
void DFS(vector<vector<vector<string>>> & graph, vector<bool> &visited, int target) {
    visited[target] = true;
    // visit adjacent nodes
    for (int i = 0; i < 26; i++) {
        if (graph[target][i].size() != 0 && visited[i] == false) {
            DFS(graph, visited, i);
        }
    }
}
 
void eulerpath(vector<vector<vector<string>>> & graph, vector<string> & res, int target) {
    // go through adjacent nodes
    stack<string> buffer;
    for (int i = 0; i < 26; i++) {
        while (graph[target][i].size() != 0) {
            buffer.push(graph[target][i][graph[target][i].size() - 1]);
            graph[target][i].pop_back();
            eulerpath(graph, res, i);
        }
    }
    while (buffer.size() != 0) {
        res.push_back(buffer.top());
        buffer.pop();
    }
}
 
void tictactoe(vector<string> & data) {
    // make graph
    vector<vector<vector<string>>> graph(26vector<vector<string>>(26vector<string>()));
    vector<int> inbound(260);
    vector<int> outbound(260);
    for (int i = 0; i < data.size(); i++) {
        int from = data[i][0]-'a';
        int to = data[i][data[i].size() - 1]-'a';
        graph[from][to].push_back(data[i]);
        outbound[from]++;
        inbound[to]++;
    }
 
    // check if graph is seperated
    vector<bool> visited(26false);
    int count = 0;
    int point = 0;
    for (int i = 0; i < 26; i++) {
        if (inbound[i]!=0&&outbound[i]!=0&&visited[i] == false) {
            point = i;
            count++;
            DFS(graph, visited, i);
        }
    }
    if (count != 1) {
        cout << "IMPOSSIBLE1" << endl;
        return;
    }
 
    // check if trail or cycle is possible
    int sc = 0;
    int start = 0;
    int lc = 0;
    int end = 0;
    for (int i = 0; i < 26; i++) {
        if (outbound[i] == inbound[i]) {
 
        }
        else if (outbound[i] == inbound[i] + 1) {
            lc++;
            start = i;
        }
        else if (outbound[i] + 1 == inbound[i]) {
            sc++;
            end = i;
        }
        else {
            cout << "IMPOSSIBLE2" << endl;
            return;
        }
    }
    // if lc or sc not balanced, return impossible
    vector<string> res;
    if (lc == 0 && sc == 0) {
        // euler cycle. start anywhere
        eulerpath(graph, res, point);
    }
    else if (lc == 1 && sc == 1) {
        // euler trail, start from start element
        graph[start][end].push_back("eraseme");
        eulerpath(graph, res, start);
        // erase eraseme
        for (int i = 0; i < res.size(); i++) {
            if (res[i] == "eraseme") {
                res.erase(res.begin() + i);
                break;
            }
        }
    }
    else {
        // not possible
        cout << "IMPOSSIBLE3" << endl;
        return;
    }
    reverse(res.begin(), res.end());
    for (string x : res) {
        cout << x << endl;
    }
}
 
int main() {
    vector<string> data = { "dog","god","dragon","need" };
    tictactoe(data);
    while(1){}
    return 0;
}
cs