[백준 C++] 1987 알파벳 - 백트래킹

1987번: 알파벳

#include <iostream>
using namespace std;

int R, C;
char Map[20][20];

char Alphabet[26];
bool Check[26];
int Max = 0;

void DFS(int Step, int Row, int Col)
{
	char Alpha = Map[Row][Col];
	if (Check[int(Alpha - 'A')])
	{
		return;
	}

	Alphabet[Step] = Alpha;
	Check[int(Alpha - 'A')] = true;
	++Step;
	if (Step > Max)
	{
		Max = Step;
	}

	// Left
	if (Col > 0)
	{
		DFS(Step, Row, Col - 1);
	}
	
	// Top
	if (Row > 0)
	{
		DFS(Step, Row - 1, Col);
	}

	// Right
	if (Col < C - 1)
	{
		DFS(Step, Row, Col + 1);
	}

	// Bottom
	if (Row < R - 1)
	{
		DFS(Step, Row + 1, Col);
	}

	Check[int(Alpha - 'A')] = false;
}

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

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

	DFS(0, 0, 0);

	cout << Max;
}

---

 

DFS & 백트래킹을 이용해서 푸는 문제입니다.

알파벳을 담은 상태배열과 현재 상태에 사용된 알파벳을 체크하는 배열을 사용해서

이미 사용된 알파벳일 때 탈출하는 조건을 포함한 깊이 우선 탐색으로 풀었습니다.

탐색 중 가장 큰 길이의 값을 갱신하고 모든 탐색이 종료되면 저장된 해당 길이를 출력하도록 했습니다.