[백준]Baekjoon1987(백 트래킹)

문제링크 : https://www.acmicpc.net/problem/1987

풀이

DFS를 통해 해결할 수 있는 문제이다.

이 때 이미 지난 알파벳을 지나지 않도록 해야하는데 이를 위해서

map을 이용해 이미 밟은 알파벳에 대해 표시할 수 있도록하였다.

#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

string arr[20];
bool check[20][20];

int move_x[] = { 1,-1,0,0 };
int move_y[] = { 0,0,-1,1 };

int r, c;
int result = 0;
map<char, int> m;
void dfs(int x, int y, int num)
{
	check[x][y] = true;
	num++;
	m[arr[x][y]]++;

	for (int i = 0; i < 4; i++)
	{
		int nx = x + move_x[i];
		int ny = y + move_y[i];
		if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
			if (m[arr[nx][ny]] == 0)
			{
				dfs(nx, ny, num);
			}
		}
	}
	result = max(result, num);
	check[x][y] = false;
	m[arr[x][y]]--;
	num--;
}
int main()
{
	scanf("%d %d", &r, &c);

	for (int i = 0; i < r; i++)
	{
		cin >> arr[i];
	}
	dfs(0, 0, 0);
	cout << result << '\n';
}