[C언어] 백준 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

예제 입력 3 

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3 

10

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

1987번: 알파벳

 

문제 풀기 전 로직 생각하기

---

좌상단부터 시작해서 상하좌우를 살펴 한 번도 보지 못한 알파벳이 있는 경우 그 인덱스로 이동하고

이 과정을 최대한 길게해서 최대 거리를 구하는 문제입니다.

 

우선 ascii  값을 따로 받는 배열로 체크하면서 이동하면 될것 같습니다.

상하 좌우를 살폈을 때 전부 이전에 봤던 알파벳인 경우 전에 있던 곳으로 이동하면서

현재 있던 곳은 체크했던 배열에서 체크를 해제하면 되겠네요.

 

전체 코드

---

#include <stdio.h>

int h, w, result = 0;
char	str[21][21];

void	dfs(int y, int x, int ret, int vis[])
{
	if (0 <= y && y < h && 0 <= x && x < w && !vis[str[y][x]])
	{
		vis[str[y][x]]++;
		ret++;
        // 결과 값이 현재까지의 길이보다 더 작은 경우 초기화
		if (ret > result)
			result = ret;
		dfs(y + 1, x, ret, vis);
		dfs(y - 1, x, ret, vis);
		dfs(y, x + 1, ret, vis);
		dfs(y, x - 1, ret, vis);
        // 상하 좌우를 살폈는데 전부 봤었던 알파벳인 경우 이전 경로로 돌아가기 전 방문 체크 해제
		vis[str[y][x]]--;
	}
}

int main()
{
	int	temp[128] = {}, ret = 0;
	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; i++)
		scanf("%s", str[i]);
	dfs(0, 0, 0, temp);
	printf("%d\n", result);
	return (0);
}

 

문제 해설

---

좌상단 부터 dfs를 시작해 본적이 없는 알파벳인 경우 체크하고 상하 좌우 깊이 우선 탐색해 줍니다.

깊이 우선 탐색을 하다가 상하좌우 전부 봤었던 알파벳이면 자연스럽게 방문 체크 해제 부분으로 내려와 해제를 해주고

이전 경로로 돌아가 다른 dfs를 반복해 줄겁니다.

 

이런 식으로 백트래킹을 구현했습니다.

 

코드는 생각보다 간결하게 구현되었지만 아쉬운 점은 프로그램 실행시간이 생각보다 많이 나왔다는 점이네요