반응형

문제 출처 :


https://www.acmicpc.net/problem/9202



알고리즘 분석 :


문제 해결에 필요한 사항

1. 트라이


이 문제는 트라이와 8방향 탐색을 이용하여 문제를 해결 할 수 있다.


우선 첫 인풋으로 들어오는 문자열들을 트라이에 넣어준다.


그 뒤 4 * 4로 들어오는 인풋에 대해 8방향 탐색을 하여 만들 수 있는 최대 8자리 문자열을 다 만들어보고 트라이에서 탐색해본다.


이때 트라이에 문자열이 존재하고(isEnd == true) 아직 이 문자열로 만들어낸 적이 없었다면(isVisited != tc)  해당하는 문자열을 정답에 갱신해주면 된다.







소스 코드 : 


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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <memory.h>
 
using namespace std;
 
const int NODE = 26;
 
int dy[8] = { -1,-1,-1,0,0,1,1,1 };
int dx[8] = { -1,0,1,-1,1,-1,0,1 };
 
char arr[10][10];
bool visit[10][10];
string maxStr;
int maxCnt, sz, total;
int tc;
struct TRIE {
    TRIE *next[NODE];
    bool isEnd;
    int isVisited;
 
    TRIE() {
        for (int i = 0; i < NODE; i++)
            next[i] = nullptr;
        isEnd = isVisited = false;
    }
    ~TRIE() {
        for (int i = 0; i < NODE; i++)
            if (next[i])
                delete next[i];
    }
};
 
bool chkRange(int y, int x)
{
    return ((0 <= x && x < 4) && (0 <= y && y < 4)) ? true : false;
}
 
void go(int y, int x, int cnt, TRIE *cur, string str) {
 
    int nowCh = arr[y][x] - 'A';
    //cout << "y :: " << y << " x ::" << x << " cnt :: " << cnt << " str :: " << str << endl;
    //    cout << "nowCh :: " << (char)(nowCh + 'A')  << endl;
    if (cnt == 8 || !cur->next[nowCh])
        return;
    if (cur->next[nowCh]->isEnd && cur->next[nowCh]->isVisited != tc)
    {
        cur->next[nowCh]->isVisited = tc;
        if (cnt + 1 == 3 || cnt + 1 == 4)
            total += 1;
        else if (cnt + 1 == 5)
            total += 2;
        else if (cnt + 1 == 6)
            total += 3;
        else if (cnt + 1 == 7)
            total += 5;
        else if (cnt + 1 == 8)
            total += 11;
 
        sz++;
        if (cnt + 1 > maxCnt) {
            maxStr = str + (char)(nowCh + 'A');
            maxCnt = cnt + 1;
        }
        else if (cnt + 1 == maxCnt) 
            if (maxStr > (str + (char)(nowCh + 'A')))
                maxStr = str + (char)(nowCh + 'A');
    }
 
    for (int i = 0; i < 8; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (!chkRange(ny, nx) || visit[ny][nx])
            continue;
 
        visit[y][x] = true;
        str += arr[y][x];
        go(ny, nx, cnt + 1, cur->next[nowCh], str);
        visit[y][x] = false;
        str.pop_back();
    }
 
}
 
int _strlen(char *tmp) {
    int len = 0;
    while (tmp[++len]) {}
    return len;
}
 
TRIE *root;
int main()
{
    root = new TRIE;
 
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        char tmp[10];
        scanf("%s", tmp);
 
        TRIE *pos = root;
        for (int i = 0; tmp[i]; i++) {
            int nowCh = tmp[i] - 'A';
 
            if (!pos->next[nowCh])
                pos->next[nowCh] = new TRIE;
 
            pos = pos->next[nowCh];
        }
 
        pos->isEnd = true;
    }
 
    int m;
    scanf("%d", &m);
 
    for(tc = 1; tc <= m; tc++)
    {
        memset(visit, 0, sizeof(visit));
        sz = maxCnt = total = 0;
        maxStr.clear();
 
        for (int i = 0; i < 4; i++)
            scanf("%s", arr[i]);
    
        for(int i = 0 ; i < 4; i++)
            for (int j = 0; j < 4; j++)
            {
                int nowCh = arr[i][j] - 'A';
                if(root->next[nowCh])
                    go(i, j, 0, root, "");
            }
        cout << total << " " << maxStr << " " << sz << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1342번] 행운의 문자열  (0) 2018.03.17
[CSAcademy] Prefix Free Subset  (4) 2018.03.11
[5446번] 용량 부족  (0) 2018.03.08
[1744번] 수 묶기  (0) 2018.03.08
[13717번] 포켓몬 GO  (0) 2018.03.07

티스토리툴바