[C++]백준 - 1987번 문제

1987번: 알파벳 (acmicpc.net)

1987번: 알파벳

 

1987번 : 알파벳

---

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

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

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

 

입력

---

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

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

백 트래킹 문제입니다.

 

우선, 그래프 탐색으로 DFS 혹은 BFS를 쓰게 될 것 같은데,

 

DFS가 훨씬 수월할 것입니다.

 

상하좌우로 DFS 탐색을 하되, 여태까지 어떤 알파벳을 밟아왔는지 알아야합니다.

 

따라서, visited라는 배열을 써서

 

26가지 알파벳 중 어떤 알파벳을 밟았는지 체크합니다.

 

백트래킹 문제이므로, DFS에서 돌아올 때는 visited를 다시 원상복구 해야합니다.

 

예시)

 

 

DFS가 C까지 탐색된 경우

 

C의 탐색을 마치고 B부터 다시 DFS를 시작하는 경우

Visited[2] = false;

B에서 E를 향해 DFS를 시작한 경우

 

 

이런 식으로 가장 멀리 간 경우를 구해서 출력하면 될 것 같습니다.

 

코드

---

#include <iostream>
#include <stack>
using namespace std;

char map[20][21];
int R, C;
int move_x[4] = { 1, 0, -1, 0 };
int move_y[4] = { 0, 1, 0, -1 };

//DFS 탐색
int dfs(pair<int, int> const& current, bool (&visited)[26])
{
	int ret = 1;
	int maxx = 0;
	for (int i = 0; i < 4; i++)
	{
		int new_x = current.first + move_x[i];
		int new_y = current.second + move_y[i];
		if (new_x < 0 || new_y < 0 || C <= new_x || R <= new_y) continue;
		if (visited[map[new_y][new_x] - 'A']) continue;
		visited[map[new_y][new_x] - 'A'] = true;
		int d = dfs({ new_x, new_y }, visited);
		visited[map[new_y][new_x] - 'A'] = false;
		if (maxx < d) maxx = d;
	}
	return ret + maxx;
}

int main()
{
	scanf("%d %d", &R, &C);

	
	for (int i = 0; i < R; i++) scanf("%s", &map[i]);

	bool visited[26] = { 0, };
	visited[map[0][0] - 'A'] = true;
	printf("%d", dfs({ 0,0 }, visited));

	return 0;
}

 

그 외

---