백준 1987 c++ "알파벳" -PlusUltraCode-

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

 

[필자 사고]

백트레킹 문제이다.

처음에는 BFS문제로 인식하고 풀다가 이러면 최대거리로 가는 경로가 만들어지지 않게 된다.

즉 백트래킹 문제로 최대로 가는 거리를 찾아야 된다.

 

교육 문제로 좋은거 같다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. Input 함수

이 함수는 전체 프로그램에서 입력을 담당한다.
사용자로부터 격자의 크기 N과 M을 입력받고, N개의 줄에 걸쳐 M개의 알파벳으로 이루어진 문자열들을 입력받아 2차원 문자 배열 형태로 저장한다.
또한, 알파벳의 방문 여부를 판단하기 위한 visited 배열의 크기를 27로 설정하고 초기화한다. (실제로는 A~Z까지만 사용되므로 26으로 해도 충분하다.)

---

2. isInside 함수

이 함수는 주어진 좌표가 격자 내부에 위치하는지를 확인한다.
행 번호와 열 번호가 각각 0 이상이며, 행은 N 미만, 열은 M 미만일 경우 true를 반환하고, 그렇지 않으면 false를 반환한다.
즉, 유효한 위치인지 경계 체크를 담당한다.

---

3. Back_Tracking 함수

이 함수는 핵심 로직으로, 현재 위치에서 상하좌우로 이동하면서 중복되지 않는 알파벳만을 밟아갈 수 있는 최대 경로의 길이를 탐색하는 백트래킹 알고리즘이다.
현재까지 밟은 칸 수가 최대값보다 크면 resultCount를 갱신한다.
그 다음, 상하좌우 네 방향으로 이동 가능한지 확인하고, 유효한 위치이며 방문하지 않은 알파벳이라면 그 알파벳을 방문 처리한 후 재귀적으로 탐색을 이어간다.
재귀 호출이 끝나면 되돌아올 때 방문 여부를 원래대로 복구하여, 다른 경로도 시도해볼 수 있도록 한다.

---

4. Game_Start 함수

이 함수는 탐색을 시작하는 지점이다.
초기 위치인 (0, 0)에 있는 알파벳을 visited 배열에 방문 처리하고, Back_Tracking 함수를 호출하여 탐색을 시작한다.
탐색이 모두 끝나면 resultCount에 담긴 최대 경로 길이를 출력한다.

[소스 코드]

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

int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

int N, M;
vector<vector<char>> arr;
vector<bool>visited;
int resultCount = 0;
void Input() {
	cin >> N >> M;
	arr.assign(N, vector<char>(M));
	visited.resize(27, false);
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int k = 0; k < M; k++) {
			arr[i][k] = str[k];
		}
	}
}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void Back_Tracking(int sero, int garo,int size) {
	if (resultCount < size) {
		resultCount = size;
	}

	for (int i = 0; i < 4; i++) {
		int nextSero = sero + dy[i];
		int nextGaro = garo + dx[i];
		if (isInside(nextSero, nextGaro) == false)continue;
		char nextCh = arr[nextSero][nextGaro];
		if (visited[nextCh- 'A'])continue;

		visited[nextCh - 'A'] = true;
		Back_Tracking(nextSero, nextGaro, size + 1);
		visited[nextCh - 'A'] = false;
	}
}

void Game_Start() {
	visited[arr[0][0] - 'A'] = true;
	Back_Tracking(0, 0, 1);
	cout << resultCount;
}

int main(void) {
	Input();
	Game_Start();
}