백준 1987 알파벳

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 R*C 칸에 알파벳들을 입력받고 좌측상단부터 출발해 이미 방문한 알파벳을 제외하고 가장 많이 방문 할 수 있는 칸을 구하는 문제입니다.

 

이동은 상하좌우로 가능하고 dfs를 이용하여 해결을 하였습니다. 

 

알파벳은 문자이므로 visited 배열에 방문 여부를 판단할때 A의 아스키 코드값인 65를 각각 값에 빼주면서 체크를 한거 이외에는 특별한 부분은 없습니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

char alpah[21][21];
int visited[26];
int nextx[4] = {1,0,-1,0};
int nexty[4] = {0,1,0,-1};
int R,C; //행과 열의 크기 
int num; //dfs를 진행하며 방문한 알파벳의 개수 
int maxnum; //방문한 알파벳의 최대 개수 

void dfs(int a, int b) {
	
	visited[alpah[a][b] - 65] = 1; //알파벳에 아스키 코드값을 빼줌 
	num++;
	
	for(int i = 0; i < 4; i++) {
		int x = a+nextx[i];
		int y = b+nexty[i];
		if(x < 0 || x >= R || y < 0 || y >= C)
			continue;
		
		if(!visited[alpah[x][y] - 65]) { //방문할 수 있으면 방문 
			dfs(x, y);
			num--; 
			visited[alpah[x][y] - 65] = 0;
		}
	}
	if(maxnum < num)
		maxnum = num;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> R >> C;
	
	for(int i = 0; i < R; i++)
		for(int j = 0; j < C; j++)
			cin >> alpah[i][j];
	dfs(0, 0);
	
	cout << maxnum;
	return 0;
}