[C++]백준1987번 알파벳

오늘은 백준1987번 알파벳 문제를 풀어보도록 하자.

일반적인 DFS문제이다. 방문처리 외 하나 더 추가할 점은 알파벳을 중복해서 거쳐갈 수 없기 때문에 alpha[26]배열을 선언하여 알파벳을 거쳐갔던 적이 있냐를 한 번 더 체크를 해주어야 한다는 점이다.

문제는 다음과 같다.

                               [접근법]

  1. 일반적인 DFS와 같다. 계속해서 cnt와 answer을 비교해주고 재귀를 통해 최댓값을 갱신해주면 된다.

                                     [코드]
#include <iostream>
#include <string>
using namespace std;

char map[20][20];
bool visit[20][20];
bool alpha[26];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int R, C, answer = -1;

bool Inbound(int y, int x) {
	return y >= 0 && y < R && x >= 0 && x < C;
}

void dfs(int y, int x, int cnt) {
	if (cnt > answer)answer = cnt;
	visit[y][x] = true; alpha[map[y][x] - 'A'] = true;
	for (int i = 0; i < 4; i++) {
		int my = y + dir[i][0];
		int mx = x + dir[i][1];

		if (Inbound(my, mx)) {
			if (!visit[my][mx] && !alpha[map[my][mx] - 'A']) {
				dfs(my, mx, cnt + 1);
				visit[my][mx] = false; alpha[map[my][mx] - 'A'] = false;
			}
		}
	}
}

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

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		string s = "";
		cin >> s;
		for (int j = 0; j < C; j++) {
			map[i][j] = s[j];
		}
	}
	dfs(0,0,1);
	cout << answer;
}