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

문제 링크: https://www.acmicpc.net/problem/1987

 

백트래킹으로 풀 수 있습니다.

백트래킹 진행할 때 방문했던 칸들의 배열을 저장할 필요 없이, 방문했던 알파벳만 저장해놓으면 됩니다. 이건 bool 배열 써도 되고, 비트마스킹 써도 되고 편한대로 구현하면 됩니다.

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };

int R, C;
int board[20][20];
int max_visited;

inline bool in_range(const int& y, const int& x) {
	return y >= 0 && y < R&& x >= 0 && x < C;
}

void backtrack(const int& alphabet, const int& y, const int& x, const int& cnt) {
	bool moved = false;

	for (int i = 0; i < 4; ++i) {
		const auto& ny = y + dy[i];
		const auto& nx = x + dx[i];
		const auto& mask = 1 << board[ny][nx];

		if (in_range(ny, nx) && !(alphabet & mask)) {
			backtrack(alphabet|mask, ny, nx, cnt + 1);
			moved = true;
		}
	}

	if (!moved)
		max_visited = max(max_visited, cnt);
}

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

	char x;
	cin >> R >> C;
	for (int i = 0; i < R; ++i)
		for (int j = 0; j < C; ++j) {
			cin >> x;
			board[i][j] = x - 'A';
		}

	const auto& alphabet = 1 << board[0][0];
	backtrack(alphabet, 0, 0, 1);
	cout << max_visited << '\n';

	return 0;
}

이게 432ms가 나왔는데 O(1) 풀이로 해도 200ms 정도는 나온다네요.

이 코드에 루프언롤링하고 범위체크하는거 빼고 등등 잡다한 최적화를 해봤더니 248ms까지는 나옵니다.

4ms 나오는 코드를 보니 getchar_unlocked를 쓰고, 함수 호출스택 대신 배열로 스택 만들어서 쓰고 뭐 그렇습니다. 저는 그렇게까지 하기는 좀.. 번거로우니 그냥 여기까지만 해야겠습니다.