[백트래킹] 1987 알파벳

 

1. 알파벳 보드 b 생성

2. 알파벳 모음 alphabets 생성 - 이미 찾은 알파벳 확인용

3. 방향 설정

        상 하 좌 우

dx = {-1, 1, 0, 0}

dy = {0, 0, -1, 1} 

 

이 보드의 (0, 0) 부터 시작해서, 

상하좌우 매번 탐색하면서

    - 보드의 바깥으로 가는 경우는 다시 돌아옴(백트랙).

    - 새로운 알파벳을 탐색했으면 기록하고, 다음 경로 탐색.

    - 이미 기록된 알파벳을 탐색했으면 백트랙.

 

ex)

 2 4

CAAB

ADCB

 

이와 같은 알파벳 보드에서, 재귀함수가 어떻게 진행되는지 보자.

C : 알파벳 체크.

  1 상 : 없음, 돌아옴

  2 하 : A 체크

    2-1 상 : C가 이미 체크 되어있음, 돌아옴

    2-2 하 : 없음, 돌아옴

    2-3 좌 : 없음, 돌아옴

    2-4 우 : D 체크

        2-4-1 상 : A가 이미 체크 되어있음, 돌아옴

        2-4-2 하 : 없음, 돌아옴

        2-4-3 좌 : A 이미 체크, 돌아옴

        2-4-4 우 : C 이미 체크, 끝 (3)

 

  3 좌 : 없음, 돌아옴

  4 우 : A 체크

    4-1 상 : 없음, 돌아옴

    4-2 하 : D 체크

      4-2-1 상 : A 이미 체크, 돌아옴

      4-2-2 하 : 없음, 돌아옴

      4-2-3 좌 : A 이미 체크, 돌아옴

      4-2-4 우 : C 이미 체크, 끝 (3)

 

    4-3 좌 : C 이미 체크, 돌아옴

    4-4 우 : A 이미 체크, 끝 (2)

 

따라서 최댓값은 3이 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int r, c;
char b[20][20];
int dx[4] {-1, 1, 0, 0};
int dy[4] {0, 0, -1, 1};
int max_ = 0;

void go(int x, int y, vector<bool> alphabets, int cnt) {
	if (x < 0 || x >= r || y < 0 || y >= c){
		return;
	}
	int idx = b[x][y] - 65;
	if (!alphabets[idx]) {
		alphabets[idx] = true;
		cnt++;
	}
	else return;

	for (int i=0; i<4; i++){
		go(x + dx[i], y + dy[i], alphabets, cnt);
	}
	if (cnt > max_) max_ = cnt;
}

int main() {
	cin >> r >> c;
	for (int i=0; i<r; i++) {
		for (int j=0; j<c; j++)
			cin >> b[i][j];
	}
	vector<bool> alphabets(26);
	go(0, 0, alphabets, 0);
	cout << max_ << '\n';
	return 0;
}

 

시간초과..??