[백준/C++] 백준 1987번: 알파벳

 

조합을 찾을 때 경우의 수가 많지 않다면 DFS를 써서 완전탐색을 하면 된다. 근데 조금만 문제가 다르게 나와도 이게 잘 생각이 안난다. 1차원배열의 조합찾기 = DFS!!!를 떠올리자. ex)비밀번호 만들기

 

알파벳의 아스키코드를 이용해서 이미 한번 사용한 알파벳은 방문처리한다. 특이점은 모든 경로 중 제일 긴 경로를 찾아야 하므로, 방문했던 알파벳은 다른 경로를 찾을 때 다시 풀어줘야 한다는 것이다.

 

#include <iostream>
using namespace std;

char map[30][30];
bool visit[26]; // 알파벳의 갯수만큼 존재 -> bool변수는 전역변수로 선언시 0으로 초기화 된다.
int Dr[] = {1, -1, 0, 0};
int Dc[] = {0, 0, 1, -1};

int R, C;
int ans = 0;

void dfs(int r, int c, int cnt) {

	if (ans < cnt) ans = cnt;

	for (int i = 0; i < 4; i++) {
		int next_r = r + Dr[i];
		int next_c = c + Dc[i];

		if (next_r < 0 || next_r >= R || next_c < 0 || next_c >= C) continue; // 이번 turn은 건너뛰자
		if (visit[map[next_r][next_c] - 'A'] == true) continue;

		visit[map[next_r][next_c] - 'A'] = true;
		dfs(next_r, next_c, cnt+1);
		visit[map[next_r][next_c] - 'A'] = false;

	}
}

int main() {

	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++)
			cin >> map[i][j];
	}

	
	visit[map[0][0] - 'A'] = true;
	dfs(0, 0, 1);
	cout << ans;

	return 0;
}