[백준] 1987 알파벳 c++

지나왔던 길에 있었던 알파벳이 없는 길로 가야한다.

최대로 지날 수 있는 칸 수를 구하면 된다.

풀이

dfs + 백트래킹
지나온 알파벳인지 체크 -> visit

 

 

#include<iostream>

using namespace std;

int graph[27][27];
bool visit[26];
int R, C;
int  ans;

void dfs(int y,int x, int cnt)
{
	
	int dx[] = { 0,1,0,-1 };
	int dy[] = { 1,0,-1,0 };
	visit[graph[y][x]] = true;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < R && nx < C && ny >= 0 && nx >= 0)//범위 안이면
		{
			if (!visit[graph[ny][nx]])//지나온 곳이 아니면
			{
				dfs(ny, nx, cnt + 1);
				visit[graph[ny][nx]] = false;// 더이상 갈 수 없을 때 돌아온다. 지나온 길에 적힌 알파벳을 다시 갈 수 있게 체크
			}
		}
	}

	if (cnt > ans)//더 이상 갈 수 없을 때 지나온 길이 최대칸수인지 확인
	{
		ans = cnt;
	}
	
	return;

}

int main()
{
	cin >> R >> C;
	string temp;
	for (int i = 0; i < R; i++)
	{
		cin >> temp;
		for (int j = 0; j < C; j++)
		{
			graph[i][j] = temp[j] - 'A';//숫자로 바꾸어서 저장

		}
	}
	dfs(0, 0,1);
	cout << ans;
	
}