백준 - 알파벳 (1987) [C++]

이 문제는 DFS를 이용해서 푸는 문제이다. 처음에는 BFS를 이용한 풀이를 시도하였으나, 구현이 복잡하고 큐에 추가적인 정보가 많이 들어가야 했다. 그래서 DFS와 백트래킹을 이용하는게 더 쉬울것 같아서 DFS로 문제를 풀었다. 이 문제에서 핵심은 visited 배열이 알파벳에 대한 visited로 만들어내는게 핵심이다. 처음에는 dfs의 매개변수로 알파벳의 방문 여부를 던져주는 방식으로 하였으나, 이는 시간 초과가 발생했다. 알파벳에 대한 visited를 이용하면 알파벳 26개가 모두 채워지면 당연히 dfs가 더 이상 진전할 수 없으므로 시간 초과가 발생하지 않는다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 20

int r, c;

int dy[] = { 1, 0, -1, 0 };
int dx[] = { 0, 1, 0, -1 };
int result = -1;

char board[MAX][MAX];
bool visited[26];

bool inRange(int y, int x)
{
	if (0 <= y && y < r && 0 <= x && x < c)
	{
		return true;
	}
	return false;
}

void dfs(int y, int x, int cnt)
{
	result = max(result, cnt);

	for (int i = 0; i < 4; i++)
	{
		int nextY = y + dy[i];
		int nextX = x + dx[i];

		if (inRange(nextY, nextX))
		{
			char next = board[nextY][nextX];

			if (!visited[next - 'A'])
			{
				visited[next - 'A'] = true;
				dfs(nextY, nextX, cnt + 1);
				visited[next - 'A'] = false;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> r >> c;

	for (int y = 0; y < r; y++)
	{
		for (int x = 0; x < c; x++)
		{
			cin >> board[y][x];
		}
	}

	visited[board[0][0] - 'A'] = true;
	dfs(0, 0, 1);

	cout << result << '\n';

	return 0;
}