c언어 1987번 알파벳 (백준)

#include <stdio.h>

int max = 0;
int r, c;
char map[21][21] = {};
char v[21][21] = {}; //방문했는가?
char a[26] = {}; //이 알파벳을 이전에 만났는가?

void dfs(int i, int j, int k) {
	if(k>=max) max = k;
	int tmp = map[i][j]-'A';
	
	if(i>=0 && i<r && j+1 < c) { //right
		if(!a[tmp] && !v[i][j]) {
			a[tmp] = 1;
			v[i][j] = 1;
			dfs(i, j+1, k+1);
			v[i][j] = 0;
			a[tmp] = 0;
		}
	}
	
	if(i>=0 && i<r && j-1 >= 0) { //left
		
		if(!a[tmp] && !v[i][j]) {
			a[tmp] = 1;
			v[i][j] = 1;
			dfs(i, j-1, k+1);
			v[i][j] = 0;
			a[tmp] = 0;
		}
	}
	
	if(j>=0 && j<c && i+1 < r) { //down
		
		if(!a[tmp] && !v[i][j]) {
			a[tmp] = 1;
			v[i][j] = 1;
			dfs(i+1, j, k+1);
			v[i][j] = 0;
			a[tmp] = 0;
		}
	}
	
	
	if(j>=0 && j<c && i-1 >= 0) { //up
		if(!a[tmp] && !v[i][j]) {
			a[tmp] = 1;
			v[i][j] = 1;
			dfs(i-1, j, k+1);
			v[i][j] = 0;
			a[tmp] = 0;
		}
	}
}

int main(void) {
	scanf("%d %d", &r, &c);
	for(int i=0; i<r; i++) {
		for(int j=0; j<c; j++) {
			scanf(" %c", &map[i][j]);
		}

	}
	
	dfs(0, 0, 0);
	
	printf("%d", max);
}

 

풀이 : 백트래킹, dfs

 

1. 문자들을 입력받는다.

2. 상하좌우로 이동할 수 있는 지를 보고, 이미 지나왔는지, 아니면 이미 만났던 알파벳인지를 확인 한다음

 조건에 만족하면 재귀함수를 또 호출 하는 형식으로 만들었다.

3. 최대 어디까지 깊숙히 들어갔는지를 max에 넣어주었다.

 

다른사람들에 비해 시간이 매우 오래걸리는 코드이므로, 다른것을 참고하는 것을 추천드립니다.

 

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

1987번: 알파벳