[백준 알고리즘] 1987번 알파벳 문제풀이 c++

DFS를 활용한 풀이다.

보드에 적혀있는 것은 알파벳대문자 A-Z이므로

bool ck[26]배열을 활용해 해당 알파벳이 사용됬는지 확인한다.

(- 'A' 를 하면 알파벳대문자 순서대로 0~25의 값이 나온다. 아스키코드)

상하좌우 위치에 해당 하는 nx,ny값이 보드의 범위 안이면서

해당 보드에 써있는 알파벳이 사용되지 않았다면

DFS를 호출한다.

cnt가 최대일 때, 말이 이동 가능한 최대의 칸 수 이다.

 

#include <iostream>

using namespace std;

int r, c, res;
char board[20][20];
bool ck[26];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

void DFS(int x, int y, int cnt){
	res = max(cnt, res);
	for(int i=0; i<4; i++){
		int nx = x+dx[i];
		int ny = y+dy[i];
		if(nx>=0 && nx<r && ny>=0 && ny<c && !ck[board[nx][ny]-'A']){
			ck[board[nx][ny]-'A'] = true;
			DFS(nx,ny,cnt+1);
			ck[board[nx][ny]-'A'] = false;
		}
	}
}

int main(){
	cin >> r >> c;
	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			cin >> board[i][j];
		}
	}

	ck[board[0][0] - 'A'] = true;
	DFS(0,0,1);

	cout << res;
	return 0;
}