[백트래킹] 백준 1987 알파벳

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

1987번: 알파벳

수행시간 : 1시간 / 난이도 : 골드 4

 

이 문제의 핵심 로직은 다음 방문할 목적지를 찾을때 조건 2가지 설정해주기, char와 bool 배열 간의 형변환(아스키코드 이용)해주기 정도. 어렵지 않게 풀 수 있는 재귀+그래프 문제.

#include <iostream>
#include <vector>
using namespace std;

int r, c;
char v_map[21][21];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
bool visited[21];
int ans = 0;

void dfs(int x, int y, int cnt) {
	if (cnt > ans) {
		ans = cnt;
	}
	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) { //조건1 : 맵안에 있어야됌
			if (visited[v_map[nx][ny] - 65] == false) { //조건2 : 내가 방문했던 알파벳이 아니여야
				visited[v_map[nx][ny] - 65] = true;
				dfs(nx, ny, cnt + 1);
				visited[v_map[nx][ny] - 65] = false;
			}
		}
	}
}

int main() {
	cin >> r >> c;
	string temp;
	for (int i = 0;i < r;++i) {
		cin >> temp;
		for (int j = 0; j < c;++j) {
			v_map[i][j] = temp[j];
		}
	}
	visited[v_map[0][0] - 65] = true;
	dfs(0, 0, 1);
	cout << ans;
}