[백준 1987] 알파벳 (C++)

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

 

문제

---

세로 𝑅칸, 가로 𝐶칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

입력

---

첫째 줄에 𝑅과 𝐶가 빈칸을 사이에 두고 주어진다. (1 ≤ 𝑅,𝐶 ≤ 20) 둘째 줄부터 𝑅개의 줄에 걸쳐서 보드에 적혀 있는 𝐶개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력

---

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

문제 풀이

---

dfs 문제.

백트래킹 방식으로 조건 충족 시 방문 여부에 체크하고 dfs함수 호출, 호출된 함수가 완료되면 방문 여부를 다시 false로 되돌려 다른 루트 탐색 시 탐색을 가능하게 한다.

또한 알파벳 역시 중복되지 않아야 하므로 방문 여부를 체크하는 배열처럼 알파벳이 적힌 칸을 지났는지를 저장하는 26자리 배열을 만들어 조건 충족 시 해당 index를 true로 변경, 호출된 함수가 완료되면 해당 index를 false로 만들도록 한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
char** arr;
bool** isVisited;
bool* isVisitedAlphabet;
int maxLength = 0;
int dx[] = {0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

void dfs(int x, int y, int length)
{
	int index = arr[x][y]-65;
	isVisited[x][y] = true;
	isVisitedAlphabet[index] = true;
	maxLength = max(length, maxLength);
	for (int i = 0; i < 4; i++)
	{
		int nextX = x + dx[i];
		int nextY = y + dy[i];
		if (nextX >= 0 && nextX <= N - 1 && nextY >= 0 && nextY <= M - 1)
		{
			if (isVisited[nextX][nextY] == false && isVisitedAlphabet[arr[nextX][nextY]-65] == false)
			{
				dfs(nextX, nextY, length+1);
				isVisited[nextX][nextY] = false;
				isVisitedAlphabet[arr[nextX][nextY] - 65] = false;
			}
		}
	}
}

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

	string str;
	cin >> N >> M;
	arr = new char* [N];
	isVisited = new bool* [N];
	isVisitedAlphabet = new bool[26];
	for (int i = 0; i < 26; i++)
	{
		isVisitedAlphabet[i] = false;
	}
	for (int i = 0; i < N; i++)
	{
		arr[i] = new char[M];
		isVisited[i] = new bool[M];
		cin >> str;
		for (int j = 0; j < M; j++)
		{
			arr[i][j] = str.at(j);
			isVisited[i][j] = false;
		}
	}
	dfs(0, 0,  1);
	cout << maxLength << "\n";
	return 0;
}