C++ / 1987 / 알파벳 ( 백트래킹 )

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

문제 요약

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

 

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

즉 같은 알파벳이 적힌 칸을 두번 지날 수 없습니다.

 

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

문제 풀이

1. 보드를 입력 받습니다.

2. dfs 함수를 만듭니다. 방문 체크 배열은 1차원으로 해당 알파벳을 들렀는지 체크합니다.

3. 함수의 매개변수로는 좌표와 갈 수 있는 길의 개수를 저장할 변수를 입력받습니다. 초기값은 1로 줍니다.

4. 현재 길의 개수와 다른  ( 이미 탐색을 마친 ) 길의 개수중에 더 큰 값을 저장합니다.

5. 탐색에서는 보드의 범위를 넘어가지 않고 방문하지 않았던 알파벳이면 탐색합니다.

6. 함수를 마치고 돌아오면 갈 수있는 다른 길을 위해 들렀던 알파벳 방문 체크를 해제 합니다.

7. 계속해서 갈 수 있는 최대 칸수가 저장됩니다.

8. 저장된 변수를 출력합니다.

주의할 점

이 문제는 dfs를 응용하는 알고리즘인 백트래킹이라는 알고리즘을 사용해서 풀어야 하는 문제입니다.

이미 들렀던 값은 다시 가지 않으며, 그중에 최댓 값을 구해야합니다.

다른 길에 최댓값이 있을 수도 있기 때문에 재귀를 마치고 돌아오면 방문 체크를 해제해주어야 합니다.

개수를  세는 cnt 변수 매개변수로 받아주면서 값을 만들어 나가야합니다.

코드

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

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

// 들렀던 알파벳 체크
bool visit[300];

int r, c;
int sum = 0, cnt = 0;
string s;
vector<vector<char>>v;

void dfs(int y, int x, int cnt)
{
	visit[v[y][x]] = true;
	// 갈 수 있는 개수가 더 큰 쪽으로 저장
 	sum = max(cnt, sum);
	//cout << x << " " << y << "\n";
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];


		if (ny >= r || ny < 0 || nx >= c || nx < 0)
		{
			continue;
		}
		if (visit[v[ny][nx]])
		{
			continue;
		}

		// 들렀던 알파벳 체크
		visit[v[ny][nx]] = true;
		dfs(ny, nx, cnt + 1);

		// 갈 수 있는 다른 경로도 체크하기 위해 알파벳 방문 체크 해제
		visit[v[ny][nx]] = false;
	}
}

int main()
{
	cin >> r >> c;
	v.resize(r, vector<char>(c));
	for (int i = 0; i < r; i++)
	{
		cin >> s;
		for (int j = 0; j < c; j++)
		{
			v[i][j] = s[j];
		}
	}
	dfs(0, 0, 1);
	cout << sum;
	return 0;
}

반응형

예제 1

2 4
CAAB
ADCB

결과 1

예제 2

3 6
HFDFFB
AJHGDH
DGAGEH

결과 2

예제 3

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

결과 3