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;
}