백준 BOJ 1987 - 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

처음 보고 든 생각은

"R과 C의 범위가 작으니까 DFS등으로도 해결할 수 있을 거 같다"

였다.

 

구현 방법은 뭐 여러가지가 있겠지만, 나는 비트마스킹을 연습할 겸

비트마스킹으로 해결해 보기로 했다.

우선 들어오는 문자들에서 'A'만큼을 빼서 0부터 시작하는 숫자로 만들어준다음

각각 0 번째 비트, 1번째 비트, .... 등으로 각각의 비트에 방문여부를 기록해준다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[25][25] = {0};
char tmp[25] = {0};
int r,c;

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

int maxv = -1;

int dfs(int x, int y, int bit, int k){
	maxv = max(maxv, k);
	for(int i=0; i<4; i++){
		int nx = x+dx[i];
		int ny = y+dy[i];
		
		if(0>=nx || nx>r || 0>=ny || ny>c) continue;
		
		if(!(bit & (1<<arr[nx][ny]))){
			dfs(nx,ny, bit | (1<<arr[nx][ny]), k+1);
		}
	}
	return 0;
}

int main(){
	scanf("%d %d", &r, &c);
	for(int i=1; i<=r; i++){
		scanf("%s", &tmp);
		for(int j=1; j<=c; j++) arr[i][j] = tmp[j-1] -= 'A';
	}
	
	//for(int i=1; i<=r; i++,puts("")) for(int j=1; j<=c; j++) printf("%d", arr[i][j]);
	
	dfs(1,1,1<<(arr[1][1]),1);
	printf("%d", maxv);
	return 0;
}

까알끔하게 AC.

자꾸 함수뒤에 return 안적어서 오류나는데 이 습관좀 고쳐야겠다....