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

알파벳으로 된 2차원배열에서 이동할 수 있는 최댓값을 구하는 문제입니다.

각 위치마다 알파벳이 있는데 이미 A라는 알파벳인 위치를 지나쳤다면,
다음에는 A라는 위치는 지나갈 수 없습니다.

DFS를 통해서 풀었고 visit배열을 통하여 알파벳을 지나쳤는지 체크해주었습니다.
그리고 DFS를 통해서 가장 큰 이동횟수가 나왔때마다 갱신해주었으며,
재귀가 끝났을 때 계산된 가장 큰 이동횟수를 출력해주었습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

int R, C;
int result = 0;
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };
int visit[26];
char map[30][30];

void solve(int a, int b, int c) 
{
	int index;
	index = map[a][b] - 65;

	if (visit[index]) {
		return;
	}
	
	visit[index] = 1;
	++c;
	result = max(result, c);

	for (int i = 0; i < 4; ++i) {
		int x = a + moveX[i];
		int y = b + moveY[i];

		if (x >= 0 && y >= 0 && x < R && y < C) {
			solve(x, y, c);
		}
	}
	visit[index] = 0;
}

int main(int argc, char *argv[])
{
	string s;

	memset(map, 0, sizeof(map));
	memset(visit, 0, sizeof(visit));

	cin >> R >> C;

	for (int i = 0; i < R; ++i) {
		cin >> s;
		for (int j = 0; j < C; ++j) {
			map[i][j] = s[j];
		}
	}

	solve(0, 0, 0);

	cout << result << endl;

	return 0;
}