[백준/BOJ] 백준 1987번 : 알파벳

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

1987번: 알파벳

알파벳 사용 여부를 저장하는 벡터를 만들고 (0,0) 위치에서 알파벳 사용이 겹치지 않는 경로중 최대 경로를 구해서 말이 지날 수 있는 가장 많은 칸 수를 구한다

 

코드

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

vector<string> board;
int r, c;
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
vector<bool> selected(26, false); //알파벳 사용 여부를 저장


int Solve(int x, int y)
{
	//(x,y)위치에서 더이상 이동 할 수 있는지 없는지 확인한다
	bool finish = true;
	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(x + dx_dy[i][0], y + dx_dy[i][1]);
		if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && selected[board[there.first][there.second] - 'A'] == false)
		{
			//갈곳이 있으므로 끝이 아니다
			finish = false;
			break;
		}
	}

	//더이상 이동할 곳이 없을때
	if (finish)
	{
		int num = 0;

		//고른 알파벳의 개수를 센다(고른 알파벳의 개수가 지나간 칸의 개수가 된다)
		for (int i = 0; i < selected.size(); i++)
		{
			if (selected[i] == true)
				num++;
		}

		return num;
	}

	int ret = 0;

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(x + dx_dy[i][0], y + dx_dy[i][1]);
		if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && selected[board[there.first][there.second] - 'A'] == false)
		{
			//there위치로 가서 탐색을 진행한다
			selected[board[there.first][there.second] - 'A'] = true;
			ret = max(ret, Solve(there.first, there.second));

			//다른 인접한 위치로 가서 탐색을 진행한다
			selected[board[there.first][there.second] - 'A'] = false;
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	string temp;

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		cin >> temp;
		board.push_back(temp);
	}

	//(0,0)위치에서 시작하므로 (0,0)위치 알파벳 사용 체크
	selected[board[0][0] - 'A'] = true;

	cout << Solve(0, 0);

	return 0;
}