1987 Alphabet
์๊ณ ๋ฆฌ์ฆ(๋ฐฑํธ๋ํน)
1. ์ด๋ค ์ํ๋ฒณ์ ๊ฒ์ฌํ๋์ง ๊ธฐ๋กํ๋ ๊ฑด check[26] ๋ฐฐ์ด์ ์ ์ธํ๊ณ , ๊ฐ ์ํ๋ฒณ์์ 65 ๊ฐ์ ๋นผ์ ๊ฐ ์๋ฆฌ๋ก ์ ๊ทผํ๋ค.('A' - 65 == 0)
2. ์ธ์ ํ ์นธ์ ๊ฒ์ฌํ๊ณ , ๊ฐ๋ฅํ๋ฉด check ํ์ํ๊ณ ์ธ์ ํ ์นธ์ผ๋ก ์ด๋. ์๋๋ฉด ๋์์์(Back Tracking) ๋ค๋ฅธ ์ธ์ ํ ์นธ ๊ฒ์ฌ
3. ๊ฐ ์ ์๋ ์ธ์ ํ ์นธ์ด ์์ผ๋ฉด ๊ทธ ์นธ์ด ๋ง์ง๋ง ์นธ์ด๋ฏ๋ก maxCount ๋ณด๋ค ํฌ๋ฉด ๊ธฐ๋ก -> ์ข
๋ฃ
4. ๋ง์ฝ deep์ด 27์ ๋ค๋ค๋ฅด๋ฉด, ์ํ๋ฒณ 26๊ฐ๋ฅผ ์ ๋ถ ๊ฒ์ฌํ ๊ฒ์ด๋ฏ๋ก, maxCount์ 26๊ธฐ๋กํ ์ข
๋ฃ
์ฝ๋
#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;
}