백준 1987번 알파벳 C++

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

 

백트래킹을 이용해서 해결할 수 있는 문제이다.

처음에 방문한 알파벳을 set에 저장해서 이미 방문한 곳인지 확인해서 풀었더니 시간초과가 났다.

그래서 알파벳 개수의 크기의 visited 배열을 만들어서 방문 체크를 O(1)에 할 수 있도록 수정했더니 통과되었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int r, c;
int ans = 0;
int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };
vector<vector<char>> board(20, vector<char>(20));
vector<bool> visited(26, false);

void BT(int row, int col, int cnt) {
	for (int i = 0; i < 4; i++) {
		int nextRow = row + dRow[i];
		int nextCol = col + dCol[i];
		if (nextRow < 0 || nextRow >= r) continue;
		if (nextCol < 0 || nextCol >= c) continue;
		char target = board[nextRow][nextCol] - 65;
		if (visited[target]) continue;
		visited[target] = true;
		BT(nextRow, nextCol, cnt + 1);
		visited[target] = false;
	}
	ans = max(ans, cnt);
}

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

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < c; j++) {
			board[i][j] = str[j];
		}
	}
	visited[board[0][0] - 65] = true;
	BT(0, 0, 1);
	cout << ans;
};