[C++] 1987: 알파벳

문제

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

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

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

입력

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

출력

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

풀이

백트래킹을 사용하여 풀었다!

각 알파벳을 방문한 적이 있는지 여부를 is_visited[26]에 저장하였다.

재귀함수를 이용하여 상하좌우로 움직인다. 해당 알파벳을 방문한 적이 없다면, 방문하고 count를 1 늘린다. count는 현재 경로까지 거리 (즉 방문한 알파벳의 개수)를 의미한다. 새로운 방문 때마다 result와 count를 비교하여 더 큰 값으로 result를 갱신한다. 현재의 recursion이 끝나면 is_visited를 0으로 돌려놓고, count도 1 빼서 재귀를 실행하기 전 상태로 돌려놓는다.

코드

#include <iostream>

using namespace std;

void input_data(void);
void recursion(int now_y, int now_x);

int r, c, result, count;
int map[20][20];
int is_visited[26];
int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};

int main(void)
{
	input_data();
	recursion(0, -1);
	cout << result << '\n';

	return (0);
}

void input_data(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> r >> c;

	int i = -1;
	while (++i < r)
	{
		int j = -1;
		while (++j < c)
		{
			char input;
			cin >> input;
			map[i][j] = input - 'A';
		}
	}

	return ;
}

void recursion(int now_y, int now_x)
{
	int i = -1;
	while (++i < 4)
	{
		int next_x = now_x + move_x[i];
		int next_y = now_y + move_y[i];
		
		if (next_x >= 0 && next_x < c && next_y >= 0 && next_y < r && !is_visited[map[next_y][next_x]])
		{
			is_visited[map[next_y][next_x]] = 1;
			count++;
			result = max(count, result);
			recursion(next_y, next_x);
			is_visited[map[next_y][next_x]] = 0;
			count--;
		}
	}

	return ;
}

성공~