[ BOJ / 완전탐색 ] 알파벳

1. 문제

---

1987번: 알파벳

 

 

2. 소스코드

---

- visited 처리를 처음엔 string으로 route를 기록하고 find로 찾았더니 시간초과가 났다.

- 그래서 visited[ 현재 문자 - 'A' ] 형식으로 수정.

- 문제를 잘못 읽어서 총 알파벳 종류가 C개인 줄로 알았는데, C개가 아니다. 직접 세야하고, 이를 이용해 백트래킹을 해주면 시간을 조금 줄일 수 있다.

- 나머지는 무난한 DFS 코드.

 

 

- 소스코드

#include <iostream>
#include <string>
#include <cstring>
#define MAX_INPUT 20
#define MAX_ALPHA 26
using namespace std;

int R, C, ans, total;
char map[MAX_INPUT][MAX_INPUT];
bool visited[MAX_ALPHA];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

void dfs(int x, int y, int temp) {
	
	if (ans == total) return;
	
	for (int i = 0; i < 4; ++i) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		char ch = map[nx][ny];
		if (nx >= R or ny >= C or nx < 0 or ny < 0) continue;
		if (visited[ch - 'A']) continue;
		visited[ch - 'A'] = true;
		dfs(nx, ny, temp + 1);
		visited[ch - 'A'] = false;
	}
	if (temp > ans) ans = temp;
	return;
}

int main() {
	cin >> R >> C;
	for (int i = 0; i < R; ++i)
		for (int j = 0; j < C; ++j) {
			cin >> map[i][j];
			if (visited[map[i][j] - 'A']) continue;
			else  ++total, visited[map[i][j] - 'A'] = true;
		}
	memset(visited, false, sizeof(visited));

	visited[map[0][0] - 'A'] = true;
	dfs(0, 0, 1);
	cout << ans << '\n';
	return 0;
}