백준 1987 알파벳

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

1987번: 알파벳

문제

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

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

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

입력

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

출력

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

예제 입력 1 

2 4

CAAB

ADCB

예제 출력 1 

3

예제 입력 2 

3 6

HFDFFB

AJHGDH

DGAGEH

예제 출력 2 

6

---

[풀이 과정]

1. 문자 하나씩 입력을 받기 위해 %1c를 해줬다.

 

2. 탐색의 시작이 (0, 0)부터이므로 arr[0][0]에 있는 알파벳은 이미 나왔다고 표시한다.

- arr[0][0]-'A'를 하면 A는 0, B는 1, C는 2 등 순서대로 숫자를 나타내게 된다.

 

3. dfs(int x, int y, int cnt)

- 상하좌우 4방향으로 다음 위치를 탐색한다.

- 다음 위치가 범위를 벗어나면 패스한다.

- 다음 위치의 알파벳이 아직 나온적 없으면 나왔다고 체크 후 dfs를 실행한다.(그 위치에서 갈 수 있는 곳 모두 탐색하기 위해)

- 최대 깊이에서의 cnt를 result와 비교 후 업데이트한다.

- dfs가 최대 깊이까지 탐색하고 나오면 해당 위치의 알파벳 체크를 지운다. (다른 경로로 탐색하기 위해) 

 

4. 최종 result값 출력한다.

---

[소스 코드]

#include <stdio.h>
const int MAX = 25;

char arr[MAX][MAX];
int n, m, alpha[30], result;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };

void dfs(int x, int y, int cnt) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
        
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        
		if (alpha[arr[nx][ny]-'A'] == 0) {
			alpha[arr[nx][ny] - 'A'] = 1;
			dfs(nx, ny, cnt+1);
			alpha[arr[nx][ny] - 'A'] = 0; # 최대 깊이까지 탐색 끝나면 체크 삭제하기
		}
	}
	if (result < cnt) result = cnt; # 최대 깊이에서의 cnt를 result에 업데이트
}
int main() {
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %1c", &arr[i][j]);
		}
	}
	alpha[arr[0][0] - 'A'] = 1;
	dfs(0, 0, 1);

	printf("%d\n", result);
	return 0;
}