백준 1987 - 알파벳

문제링크

• 백준 1987

문제설명

• R x C 크기의 격자 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단은 (1,1)부터 시작하고 해당 위치에 말이 놓여 있다.
• 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있다.
• 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.
  • 같은 알파벳이 적힌 칸을 두 번 지날 수는 없다.
• 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 갈 수 있는지 구하라

문제접근

• DFS 와 백트래킹 으로 푼다.
  • DFS 는 하나의 길을 선택해서 끝까지 탐색하고 돌아오는 알고리즘이다.
  • DFS 와 BFS 모두 완전탐색 알고리즘이지만, DFS 는 하나의 경로를 완성한 후 그 다음 경로를 찾는 반면, BFS 는 모든 경로에 대해 한칸씩 탐색하는 방법이다.
  • 이번 문제처럼 시작점 하나를 잡고, 가장 긴 경로를 찾아야 하는 문제는 DFS 가 유리하다.
  • BFS 는 한 점에서 다른 점까지의 거리를 파악하는 문제에서 유용하다.
  • 가능한 모든 경로를 찾아야하므로 백트래킹 기법을 적용한다.
• 시간초과에 유의해야 한다. 즉, 비효율적인 재귀호출은 최대한 줄여야 한다.
• history[26] 1차원 배열을 선언해서 문자의 등장 여부를 확인한다. 0인 경우 등장한 적이 없는 문자이고, 1인 경우 등장한 적이 있는 문자이다.
• history[26] 배열이 방문표시를 하는 역할을 대신한다. 이미 등장한 문자는 이미 배열에 1로 표시되어 있기 때문에 방문할 수 없기 때문이다.
• 다음 칸으로 이동할 때 마다(재귀호출이 이루어질 때 마다) 이동한 칸수를 최대 칸수와 비교하며 갱신한다.

구현

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

typedef struct _pos {
	int xpos, ypos;
	char ch;
} Pos;

int N, M, ans = 0;
bool visited[20][20];
vector<string> board;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void dfs(int x, int y, vector<int> history, char ch, int dist) {
	ans = max(ans, dist);
	for (int dir = 0; dir < 4; dir++) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		if (history[board[nx][ny]-'A']==1) continue;
		history[board[nx][ny] - 'A'] = 1;
		dfs(nx, ny, history, board[nx][ny], dist + 1);
		history[board[nx][ny] - 'A'] = 0;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N >> M;
	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		board.push_back(str);
	}
	vector<int> history(26, 0);
	history[board[0][0] - 'A'] = 1;
	dfs(0, 0, history, board[0][0], 1);
	cout << ans << endl;
	return 0;
}