백준1987 - 알파벳

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

1987번: 알파벳

dfs와 비트마스킹을 활용한 문제다. 문제에서 주어진 조건은 전에 찾은 알파벳을 다시 찾으면 안된다는 조건이 있었기 때문에 비트마스킹을 활용하였다. 중요한 것은 내가 처음에 갔던 방향이 무조건 최대의 알파벳 갯수를 찾는다는 보장이 없다는 것이다. 그 점 때문에 내가 현재 이동한 좌표가 방문처리가 끝나면 다시 미방문 처리를 하고 알파벳 또한 못 찾은 것으로 비트마스킹하여 다음 탐색에서 방문할 수 있도록 해야한다는 점을 잊지 말아야한다. 그 점만 지키면 풀 수 있다.

#include <iostream>
#include <string>
using namespace std;

char visit[21][21]; //방문 여부
char mat[21][21]; //알파벳이 존재하는 위치
bool alphabet[26]; //알파벳 비트 마스킹

//4방향으로 이동을 표현
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int ans = 0; //최대 알파벳 갯수

int m, n; //주어진 알파벳 행렬의 크기(세로 m, 가로 n)
string s; //입력

void dfs(int x, int y, int cnt) {
	alphabet[mat[x][y] - 'A'] = true;
	visit[x][y] = true;
	if (cnt > ans) {
		ans = cnt;
	}
    //4방향으로 방문 시작, 주어진 행렬 안에 존재하고 전에 방문한 공간이 아니고 전에 찾았던 알파벳이 아니면 이동
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (1 <= nx && nx <= m && 1 <= ny && ny <= n && !alphabet[mat[nx][ny] - 'A'] && !visit[nx][ny]) {
			dfs(nx, ny, cnt + 1);
			visit[nx][ny] = false; //이동한 행렬에서 미방문 처리
			alphabet[mat[nx][ny] - 'A'] = false; //이동한 행렬에 있는 알파벳을 못 찾은 것으로 다시 비트 마스킹
		}
	}
}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		for (int j = 0; j < n; j++) {
			mat[i][j + 1] = s[j];
		}
	}

	dfs(1, 1, 1); //1, 1에서 시작하고 처음에는 무조건 자기 자신은 찾으니까 1로 세팅

	cout << ans;
}