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

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

1987번: 알파벳

---

접근 방식

백 트래킹을 이용해서 문제를 해결하였다.

먼저 특정 알파벳이 포함 되었는지, 안 되었는지 구분할 bool형 배열을 만들어준다.

(1,1)지점은 무조건 지나가게 되므로 (1,1)지점에 있던 알파벳은 지나갔다고 표시를 해주고, (1,1) 지점부터 4 방향으로 탐색을 해준다. 

탐색이 가능한 조건(배열 내에 해당, 이미 지나가지 않은 알파벳)을 만날 경우에 다시 그 지점으로부터 탐색을 해준다.

이 과정을 반복해주면 쉽게 문제를 해결해 줄 수 있다.

---

#include<iostream>
#include<queue>
#include<cmath>
#include<string>
#include<stack>
#include<vector>
#include<cmath>
#include<tuple>
using namespace std;
int n, m;
char arr[21][21];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int maxDepth;
bool check[27];
void DFS(int x, int y,int depth) {
	if (depth > maxDepth)maxDepth = depth;
	for (int i = 0; i < 4; i++) {
		int x2 = x + dx[i];
		int y2 = y + dy[i];
		if (x2 > 0 && y2 > 0 && x2 <= n && y2 <= m && !check[arr[x2][y2] - 'A']) {
			check[arr[x2][y2] - 'A'] = true;
			DFS(x2, y2,  depth + 1);
			check[arr[x2][y2] - 'A'] = false;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	check[arr[1][1]-'A'] = true;
	DFS(1, 1, 1);
	cout << maxDepth;
}

---

기존 백 트랙킹 문제에서, 살짝만 변형된 문제였다.