1987 Alphabet
알고리즘(백트래킹)
1
2
3
4
1. 어떤 알파벳을 검사했는지 기록하는 건 check[26] 배열을 선언하고, 각 알파벳에서 65 값을 빼서 각 자리로 접근한다.('A' - 65 == 0)
2. 인접한 칸을 검사하고, 가능하면 check 표시하고 인접한 칸으로 이동. 안되면 돌아와서(Back Tracking) 다른 인접한 칸 검사
3. 갈 수 있는 인접한 칸이 없으면 그 칸이 마지막 칸이므로 maxCount 보다 크면 기록 -> 종료
4. 만약 deep이 27에 다다르면, 알파벳 26개를 전부 검사한 것이므로, maxCount에 26기록후 종료
코드
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
#include <iostream>
#include <cstring>
#define MAX_WIDTH 20
#define ASCII_A 65
using namespace std;
char map[MAX_WIDTH][MAX_WIDTH];
bool check[26];
int height, width, maxCount = 0;
void DFS(int row, int col, int deep);
int main() {
cin >> height >> width;
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
cin >> map[i][j];
check[map[0][0] - ASCII_A] = true;
DFS(0,0,1);
cout << maxCount;
}
void DFS(int row, int col, int deep) {
if (deep == 27) {
maxCount = deep-1;
return;
}
bool isEnd = true;
if (col < width - 1 && check[map[row][col + 1] - ASCII_A] == false) {
check[map[row][col + 1] - ASCII_A] = true;
DFS(row, col + 1, deep + 1);
check[map[row][col + 1] - ASCII_A] = false;
isEnd = false;
}
if (row < height - 1 && check[map[row + 1][col] - ASCII_A] == false) {
check[map[row + 1][col] - ASCII_A] = true;
DFS(row + 1, col, deep + 1);
check[map[row + 1][col] - ASCII_A] = false;
isEnd = false;
}
if (col > 0 && check[map[row][col - 1] - ASCII_A] == false) {
check[map[row][col - 1] - ASCII_A] = true;
DFS(row, col - 1, deep + 1);
check[map[row][col - 1] - ASCII_A] = false;
isEnd = false;
}
if (row > 0 && check[map[row - 1][col] - ASCII_A] == false) {
check[map[row - 1][col] - ASCII_A] = true;
DFS(row - 1, col, deep + 1);
check[map[row - 1][col] - ASCII_A] = false;
isEnd = false;
}
if (isEnd)
maxCount = maxCount > deep ? maxCount : deep;
}