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

문제

https://www.acmicpc.net/problem/1987

1987번: 알파벳

풀이

DFS를 사용하는 방법으로 문제에 접근하였다.

보드의 문자 - 'A'가 0 ~ 25인점을 이용하여 26의 크기를 가진 방문 여부 배열을 만들어주었고 DFS를 돌리며 매 DFS마다 칸 수를 최댓값으로 초기화 시켜주었다. 이후 DFS가 끝나면 최댓값을 출력해주면 된다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int result = 0;
char board[21][21];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool isused[26];

void func(int x, int y, int cnt)
{
	result = max(result, cnt);

	for (int dir = 0; dir < 4; dir++)
	{
		int nx = x + dx[dir];
		int ny = y + dy[dir];

		if (nx < 0 || nx >= n || ny < 0 || ny >= m)
		{
			continue;
		}

		if (!isused[board[nx][ny] - 'A'])
		{
			isused[board[nx][ny] - 'A'] = true;
			func(nx, ny, cnt + 1);
			isused[board[nx][ny] - 'A'] = false;
		}
	}
}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
		}
	}

	isused[board[0][0] - 'A'] = true;
	func(0, 0, 0);

	cout << result + 1;
}