[BOJ] 1987 알파벳

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

1987번: 알파벳

 

알고리즘: DFS, Backtracking

 

---

접근:

1. 경로 탐색 문제

2. 같은 알파뱃이 적힌 칸은 두 번 지날 수 없다

3. 최대한 몇 칸을 지날 수 있는가

 

->

1, 3번 조건을 보면 이 문제가 DFS 문제라는 것을 알 수 있다. (경로를 탐색해가면서 최장경로 찾기)

이제 2번 조건만 해결해주면 된다.

 

2번은 조건은 알파뱃과 숫자를 하나씩 대응시켜 (A-0, B-1, C-2, ..., )

한 칸씩 나아갈 때마다 해당하는 배열 인덱스를 체크하는 방식을 통해 해결하였다.

 

주의)

경로 탐색 문제라고 BFS로 접근하기에는 메모리 관리가 쉽지 않을 것이다...

bit 연산을 이용한다 해도, map[R][C][2^26-1] ... -> 20*20*2^26;;; 메모리가 어마무시하다.

 

// 1987: 알파벳

#include<iostream>
#include<bitset>
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;
typedef pair<int, int> ii;

int R, C, map[21][21], ans;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
bool chk[30];
char ch;

void DFS(int y, int x, int cnt)
{
	int ny, nx;
	
	for (int i = 0; i < 4; i++)
	{
		ny = y + dy[i];
		nx = x + dx[i];
		if (ny < 0 || ny >= R || nx < 0 || nx >= C || chk[map[ny][nx]]) continue;
		chk[map[ny][nx]] = 1;		// check on
		DFS(ny, nx, cnt+1);
		chk[map[ny][nx]] = 0;		// check off
	}
	
	ans = MAX(ans, cnt);
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> R >> C;
	
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> ch;
			map[i][j] = ch - 'A';
		}
	}
	chk[map[0][0]] = 1;
	DFS(0, 0, 1);
	
	cout << ans;
	return 0;
}