[백준 BOJ/C++] 1987 알파벳

 

1987번: 알파벳

 

백트랙킹, DFS를 연습하기 적당한 문제다.
요구사항이 복잡하거나 구현량이 많지 않고 중복된 알파벳을 피해서 가장 멀리 갈 수 있는 경로를 찾아야 한다.

 

 

알파벳으로 채워진 맵에서 같은 알파벳을 중복하지 않게 방문하여 갈 수 있는 최대 거리를 구하는 문제다.

시작점은 항상 (0, 0) 이며 상하좌우 한 칸 씩 탐색해 나가면 된다.

 

 

몇 몇 실수하기 쉬운 부분이 있는지 정답 비율이 낮은 편이지만 복잡한 문제는 아니라서 백트랙킹, DFS 문제와 관련해 기본기를 쌓기 좋은 문제다.

 

 

---

 

 

문제의 포인트

 

백트랙킹 알고리즘
알파벳의 중복 피하기

 

 

백트랙킹 알고리즘

 

DFS, Backtracking, 출처 - Wikipedia

 

일반적으로 맵 형태의 입력이 주어지고 이동시켜가는 문제는 BFS든 DFS든 탐색 알고리즘을 이용해야하는 경우가 많다.

최단 경로를 찾아야 하는 경우 BFS를 통해 여러 방향의 탐색을 같은 깊이로 탐색시켜가면서 가장 먼저 도달하는 경로를 발견하도록 하는 것이 효과적이다.

 

 

그 외에 N-Queen 문제와 유사하게 일단 갈 곳을 선택하면서 끝까지 탐색해보는 방식이 필요한 문제는 DFS 혹은 이를 활용한 Backtracking 방식으로 접근하는 것이 좋다.

 

 

이 문제의 경우 경로를 찾는 과정이기 때문에 BFS를 통해 찾아갈 수도 있겠지만 목표지점에 도착하면 나머지 탐색을 무시하고 끝낼 수 있는 최단 경로 탐색이 아니라 어쨌든 갈 수 있는 최대한을 가봐야 하는 상황이므로 Backtracking 이 더 적합한 접근이라고 할 수 있다.

 

 

일단 한 방향으로 끝까지 가보고 중복된 알파벳으로 둘러 쌓여 더이상 갈 곳이 없다면 마지막 분기점으로 돌아가 안가본 다른 길을 통해 탐색해가는 방법으로 접근하면 된다.

 

 

DFS나 Backtracking 구현에 익숙하지 않다면 한칸 나아가서 경로를 선택할 때 필요한 정보와 선택할 내용이 무엇인지 생각해보면 좋을 것 같다.

 

 

필요한 정보 : 현재 위치, 지나온 칸의 수
선택할 내용 : 다음 이동할 방향
선택 기준 : 이미 지나온 알파벳과 중복 여부

 

 

우선 필요한 정보는 현재 위치와 지나온 칸의 갯수다.

현재 위치를 알아야 맵에서 다음 이동 후보를 알 수 있고 지나온 칸의 수를 세고 있어야 최대 칸 수를 알 수 있다.

이러한 필요 정보는 재귀 함수에 전달할 인자로 이용하면 된다.

각 1번의 재귀함수 호출은 1번의 선택과 이동으로 생각하면 생각하기 쉬워진다.

 

 

재귀 함수에서 선택할 내용은 인접한 4 방향 중 다음으로 이동할 방향이다.

그리고 여기에는 이미 지나온 알파벳과 중복되는지 여부가 판단 기준이 된다.

즉, 재귀 함수 내에서는 4 방향 중 중복 여부를 판단해 다시 재귀 호출 시켜주면 된다.

 

 

알파벳의 중복 피하기

 

문제는 어떻게 중복된 알파벳을 피해서 재귀 호출을 시킬것인가 하는 부분이다.

일반적으로 맵을 받아 탐색하면서 지나온 길을 표시하기 위해서 맵과 같은 크기의 visit 배열 등을 활용한다.

여기에 지나온 길을 표시해주고 갈 방향을 선택할 때 참조하면 쉽게 같은 길을 반복하지 않게 할 수 있다.

비슷하게 알파벳 A ~ Z까지 지나왔던 알파벳을 26개의 배열에 표시해주기만 한다면 간단히 중복을 피해갈 수 있다.

 

 

visit 배열에 선택할 알파벳을 의미하는 칸에 표시를 해두고 재귀함수를 태웠다면 함수 return 이후에는 visit 배열에 표시해줬던 칸을 다시 지워줘야 한다.

갈 데 까지 가보는 깊이 우선 탐색에서 재귀 함수가 리턴하고 다음줄을 수행한다는 것은 그 길로는 끝까지 탐색해보고 다시 그 선택지로 돌아와 다른 방향으로 탐색해보는 의미이기 때문이다.

 

 

---

 

전체 Code

#include <iostream>
#include <algorithm>

using namespace std;

int R, C, max_cnt;

char map[20 + 10][20 + 10];
int visit[30];

int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

void DFS(int r, int c, int cnt) {
	int i, next_r, next_c;

	if (cnt > max_cnt)
		max_cnt = cnt;

	if (r == R && c == C)
		return;

	for (i = 0; i < 4; i++) {
		next_r = r + dr[i];
		next_c = c + dc[i];

		if (next_r < 0 || next_r >= R || next_c < 0 || next_c >= C) continue;
		if (visit[map[next_r][next_c] - 'A'] > 0) continue;

		visit[map[next_r][next_c] - 'A'] = 1;
		DFS(next_r, next_c, cnt + 1);
		visit[map[next_r][next_c] - 'A'] = 0;
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i, j;

	cin >> R >> C;

	for (i = 0; i < R; i++) {
		for (j = 0; j < C; j++) {
			cin >> map[i][j];
		}
	}

	visit[map[0][0] - 'A'] = 1;
	DFS(0, 0, 1);
	cout << max_cnt << "\n";

	return 0;
}