[백준] 1987번 알파벳

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

1987번: 알파벳

재귀로 순열, 조합 풀듯이 풀었다. 방문한 뒤에 다시 visited를 false로 바꿔주었다. 한 번 방문했다고 다시 방문을 못하면 그것은 백트래킹이 아니라 DFS이기 때문이다.

#include <vector>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

int dr[] = { 1, -1, 0, 0 };
int dc[] = { 0, 0, 1, -1 };
int n, m;
vector<vector<char>> v;
int maxNum = 0;
vector<bool> visited(26);

void dfs(int r, int c, int num) {
	if (num> maxNum)
		maxNum = num;
	for (int i = 0; i < 4; i++) {
		int row = r + dr[i];
		int col = c + dc[i];
		if (row >= n || col >= m || row < 0 || col < 0 || visited[v[row][col] - 'A'])
			continue;
		visited[v[row][col] - 'A'] = true;
		dfs(row, col, num + 1);
		visited[v[row][col] - 'A'] = false;
		
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	v = vector<vector<char>>(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
		}
	}
	visited[v[0][0] - 'A'] = true;
	dfs(0, 0, 1);
	cout << maxNum;
	return 0;
}