1937번: 알파벳

문제 설명

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

1987번: 알파벳

[문제]

 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

[입력]

 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

[출력]

 첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

[예제 입력 1]

2 4
CAAB
ADCB

[예제 출력 1]

3

---

풀이

 알맞은 자료 구조 선택에 고생을 했던 문제이다. 문제 자체는 단순히 주어진 2차원 형태의 문자열 상에서, 특정 문자가 중복되지 않게 이동할 수 있는 최대 횟수를 구하는 것으로 어렵지는 않은 편이다. 특히 이런 이동 문제에서 고려되는 특정 위치 방문 여부(흔히 visited 배열로 구분)가 문제에서 구해야 하는 정답에 포함되어 있는 개념이라 구현 자체는 어렵지 않다.

 일단 문제에서 한 번 탐색을 시작하면 해당 경로의 끝까지 탐색을 진행해서 해당 경로의 길이를 알아야 했기에 BFS가 아닌 재귀 형태의 DFS로 구현을 했다. 이후 이 과정에서 탐색 시간을 줄이기 위해 백트래킹을 구현하고자 해당 탐색에서만 특정 위치의 방문 여부를 표시하고 이후엔 해당 여부를 초기화하는 과정을 적용했다.

유의할 점

 앞서 설명한 방문 여부와 백트래킹 구현 과정에서 다양한 실패를 경험했다. 우선적으로는 unordered_set을 통해 지나간 경로의 알파벳을 저장하고, 해당 위치에서 탐색이 끝나면 unordered_set에서 해당 위치의 알파벳을 제거하는 것으로 방문 여부와 백트래킹을 구현했는데 시간 초과를 먹었다. 여기서 단순히 unordered_set에서 알파벳을 탐색하는 것이 오래 걸리는 것인가 착각하여 재귀 호출을 할 때마다 unordered_set을 복사하고 복사한 변수에 알파벳을 추가하는 것으로 구현을 했더니 이 또한 시간 초과를 먹고 말았다.

 그리고는 방문 여부에 대한 자료 구조를 unordered_set이 아닌 알파벳 26자 길이의 벡터로 변경, 이를 재귀 호출마다 벡터를 복사해서 넘기는 방식으로 구현했더니 시간 초과를 당했고, 최종적으로는 하나의 벡터만을 이용하여 해당 요소를 표시했다 지우는 것으로 구현했더니 최종 통과를 할 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<char>> map;

int DFS(int R, int C, int r, int c, vector<bool>& visited) {//DFS 탐색
	int result;

	if (0 > r || r >= R || 0 > c || c >= C)//위치 검사
		return 0;

	int pos = map[r][c] - 'A';

	if (visited[pos] == true)//알파벳 중복
		return 0;
	else {//새로운 알파벳일 경우
		visited[pos] = true;//해당 탐색 체크

		result = DFS(R, C, r + 1, c, visited);
		result = max(result, DFS(R, C, r, c + 1, visited));
		result = max(result, DFS(R, C, r - 1, c, visited));
		result = max(result, DFS(R, C, r, c - 1, visited));

		visited[pos] = false;//탐색 해제

		return 1 + result;
	}
}

int main() {
	vector<bool> visited(26, false);//각 알파벳 중복 검사 벡터
	int R, C;
	int answer;
	cin >> R >> C;

	for (int i = 0; i < R; i++) {//보드 초기화
		vector<char> temp;
		string elem;
		cin >> elem;
		for (int j = 0; j < C; j++) {
			temp.push_back(elem[j]);
		}
		map.push_back(temp);
	}

	answer = DFS(R, C, 0, 0, visited);

	cout << answer;

	return 0;
}

//초기엔 unordered_set을 통해 알파벳 입력과 삭제를 반복 -> 시간 초과
//이후 unordered_set을 복제하고 넘기는 방식 -> 시간 초과
//길이 26의 벡터를 복제하고 넘기는 방식 -> 시간 초과
//최종 길이 26의 벡터를 체크하고 해당 부분 탐색 완료후 체크 해제 방식 -> 통과

---

결과