6) 백준 1987 - 알파벳

<문제>

www.acmicpc.net/problem/1987

1987번: 알파벳

다 풀었다.... 는 통수 딱!!!!! (85% 에서 헤맸다....ㅠㅠㅠ)

 

<코드 - 1>

#include <iostream>
#include <vector>

using namespace std;

vector<char> road;

int R, C;
int answer = 1;
char map[21][21];
bool check[21][21] = {0, };

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

void dfs(int cnt, int x, int y) {
	char letter = map[x][y];
	for(int i = 0; i < road.size(); i++) {
		if(letter == road[i]) {
			answer = max(cnt, answer);
			return;
		}
	}
	
	road.push_back(letter);
	check[x][y] = 1;
	
	for(int i = 0; i < 4; i++) {
		if((x + dx[i]) <= R && (y + dy[i]) <= C 
		&& (x + dx[i]) > 0 && (y + dy[i]) > 0
		&& !check[x + dx[i]][y + dy[i]]) {
			dfs(cnt+1, x + dx[i], y + dy[i]);
		}
	}
	if(cnt+1 == R*C) {
		answer = cnt+1;
	}
	check[x][y] = 0;
	road.pop_back();
}

int main(void) {
	cin >> R >> C;

	for(int i = 1; i <= R; i++) {
		for(int j = 1; j <= C; j++) {
			cin >> map[i][j];
		}
	}
	
	dfs(0, 1, 1);
	
	cout << answer << endl;
	
	return 0;
}

방법은 road라는 이름을 가진 vector에다 경로를 넣고 빼주면서 check에다가 지나간 경로를 체크해줬다. (check는 왔던길 다시 안가도록 해주기 위함 이랄까)

그리고 dfs를 계속 돌리면서 다음에 오는 문자가 경로에 이미 있나 road를 돌려서 확인. 있으면 cnt값을 그대로 answer과 비교하여 큰 값을 저장한다.

이를 할 수 있을 때 까지 계속 돌아가면 정답이 된다.

 

주의할 점이 있는데 이건 다음 코드를 설명 한 후에 하겠다.

 

<코드 - 2>

#include <iostream>
#include <vector>

using namespace std;

int R, C;
int answer = 1;
char map[21][21];
bool check[21][21] = {0, };
bool alph_check[26] = {0, };

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

void dfs(int cnt, int x, int y) {
	char letter = map[x][y];
	if(alph_check[letter-65]) {
		answer = max(answer, cnt);
		return;
	}
	
	alph_check[letter-65] = 1;
	check[x][y] = 1;
	
	for(int i = 0; i < 4; i++) {
		if((x + dx[i]) <= R && (y + dy[i]) <= C 
		&& (x + dx[i]) > 0 && (y + dy[i]) > 0
		&& !check[x + dx[i]][y + dy[i]]) {
			dfs(cnt+1, x + dx[i], y + dy[i]);
		}
	}
	if(cnt+1 == R*C) {
		answer = cnt+1;
	}
	check[x][y] = 0;
	alph_check[letter-65] = 0;
}

int main(void) {
	cin >> R >> C;

	for(int i = 1; i <= R; i++) {
		for(int j = 1; j <= C; j++) {
			cin >> map[i][j];
		}
	}
	
	dfs(0, 1, 1);
	
	cout << answer << endl;
	
	return 0;
}

코드1번과 방법은 비교하다. 다만, vector대신 배열을 썼다.

중복됬는지 확인 할 때, A(index = 0) 부터 Z(index = 25)까지 비교하는 대상의 배열에 가서 true값이면 이미 왔다는 뜻으로 똑같이 answer과 비교하여 넣어주면 된다.

vector을 사용했을 때 보다 훠~~~~얼씬 빨랐다.

 

<주의>

85%에서 계속 걸렸다.

1. 입력값이 다음과 같다고 가정해보자.

1 1
A

answer = 0; 으로 설정해놓으면 0이 아닌 1이 출력된다. 조심하자.

(본인의 코드에서는 굳이 answer = 1;로 안해도 if(cnt+1 == R*C)에서 걸러진다.)

 

2. 입력값이 다음과 같다고 가정해보자.

1 3
ABC

 

answer = 1; 으로 설정했을 때, 1이 출력될 것이다.

if(cnt+1 == R*C)를 넣어줘서 올바른 값(위의 경우에는 3)을 구해내야한다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

거의 끝자락에서 틀렸다면 경계값을 조사해보자!!!

어렵다 ㅠㅠㅠㅠㅠㅠ

 

<시간 비교>

근데! 이 마저도 절반으로 줄일 수 있나보다....

대단해......