백준 1987

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

이 문제의 경우 그냥 쉬운 DFS였다 골드 4라고하기에는 많이 애매한 문제라고 생각되어진다.
DFS와 단짝인 백트래킹과 조건 검사식만 설정해주면 되는 문제였다.

 

#include<iostream>
using namespace std;
int isVisited[20][20];
bool isUsed[26];
char arr[20][20];
int maxNum = 0;
int GetIdxOfAlphabet(char ch);
bool isCanGo(int idxX, int idxY) {
	if (idxX < 0 || idxY < 0 || idxX>19 || idxY > 19 || (isVisited[idxX][idxY] == true) || (isUsed[GetIdxOfAlphabet(arr[idxX][idxY])]==true)) {
		return false;
	}

	return true;
}
void dfs(int startX, int startY, int cnt) {
	if (!isCanGo(startX, startY)) {
		if (cnt-1 > maxNum) {
			maxNum=cnt-1;
			return;
		}
	}
	else {
		isUsed[GetIdxOfAlphabet(arr[startX][startY])] = true;
		isVisited[startX][startY] = true;
		dfs(startX + 1, startY, cnt + 1);
		dfs(startX -1, startY, cnt + 1);
		dfs(startX, startY+1, cnt + 1);
		dfs(startX, startY-1, cnt + 1);
		isUsed[GetIdxOfAlphabet(arr[startX][startY])] = false;
		isVisited[startX][startY] = false;
	}
}

int GetIdxOfAlphabet(char ch) {
	if (ch >= 'A' && ch <= 'Z') {
		int position = ch - 'A';
		return position;
	}
	else
		return 0;
}
int main() {
	int r, c;
	cin >> r >> c;
	char inputString[21];
	for (int i = 0; i < r; i++) {
		cin >> inputString;
		for (int j = 0; j < c; j++) {
			arr[i][j] = inputString[j];
		}
	}
	dfs(0, 0, 1);
	cout << maxNum;
	return 0;
}

 

이 문제의 경우 입력 string으로 받을 시 문제가 생겨서 해당 부분을 char 배열을 입력받도록 변경하였습니다.
또한 항상 이전에 dfs를 풀때 조건식을 위에다가사용했을 때 너무 복잡해지는 현상이 있어 함수로 해당 부분을 따로 정ㄴ리해 놓았습니다

 

DFS에서 항상 중요한건 방문했다가 나오면 다시 배열들을 초기화 해줘야 한다는 것입니다