1987 알파벳

1987번: 알파벳

전형적인 DFS 문제이다. 리트코드에서 DFS 사용하는 문제랑 비교도 할 수 없을 정도로 단순하게 입력받아서

DFS 돌리면 된다.

 

그런데 이거 의외로 시간 복잡도가 빡빡해서 DFS 내부적으로 쓰이는 연산은 가벼운 걸로 수행해야 했었다.

그냥 아무 생각 없이 map 사용하고, 매번 map 복사하니까 바로 시간 초과가 났다...

그래서 그냥 배열 써버리고 재사용하니까 여유롭게 통과됐다.

 

C++

#include <iostream>

using namespace std;

int res{}, r, c;
pair<int, int> step[4] = { {0,1}, {0, -1}, {-1,0}, {1,0} };
string str[20];
bool check[26];

void dfs(int i, int j, int cnt) {
	check[str[i][j] - 'A'] = 1;
	if (cnt > res)
		res = cnt;
	int next_i, next_j;
	for (auto s : step) {
		next_i = i + s.first;
		next_j = j + s.second;
		if (next_i >= 0 && next_i < r && next_j >= 0 && next_j < c && !check[str[next_i][next_j] - 'A']) {
			check[str[next_i][next_j] - 'A'] = true;
			dfs(next_i, next_j, cnt + 1);
			check[str[next_i][next_j] - 'A'] = false;
		}
	}
}
int main(void)
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	cin >> r >> c;

	for (int i = 0; i < r; ++i)
		cin >> str[i];

	dfs(0, 0, 1);

	cout << res;

	return 0;
}