[백준 1987] 알파벳

문제(복붙)

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

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

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

아이디어

DFS라는 생각이 들긴 했다. 하나의 PATH에 대해 HIST를 갖고 있어야 다음 노드를 방문할지 결정할 수 있기 때문이다. 마침 배열 사이즈도 400이라서.. DFS로 풀만 하다는 생각을 했다.

단, 재귀로 DFS를 구현하기

재귀를 활용해서 짜면 하나의 hist에 dfs레벨이 내려가면 썼다가, 올라오면 지웠다가 하는 게 가능하다.

오답 : Stack 활용한 DFS

스택을 활용해서 스택에 방문할 노드들과 함께 자신의 hist까지 저장하는 방법이다. 18퍼센트에서 시간초과를 받았다.

이거 때문에 candi 객체에서 = 연산자의 deepcopy까지 구현했었다;;
deepcopy를 하는 과정에서 시간초과가 발생했던 거 같다.

dfs로 푸는 게 맞는 거 같은데(배열 사이즈로보나 문제로 보나..) 틀렸을 때는 dfs의 다른 스타일을 써보려는 시도를 해야겠다고 생각했다.

오답코드는 맨하단에 작성

정답코드(재귀 활용 DFS)

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int r, c;
char tab[20][20];
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };

bool inbox(int i, int j) {
	return i >= 0 && i < r&& j >= 0 && j < c;
}
int max_depth = 0;
void dfs(int ci, int cj,vector<bool> &hist,int depth) {
	max_depth = max(max_depth, depth);

	//child 검사
	for (int k = 0; k < 4; k++) {
		if (inbox(ci + di[k], cj + dj[k])) {
			int child_char = tab[ci + di[k]][cj + dj[k]];
			if (hist[child_char - 'A'] == false) {
				hist[child_char - 'A'] = true;
				dfs(ci + di[k], cj + dj[k], hist, depth + 1);
				hist[child_char - 'A'] = false;
			}
		}
	}
}
int main() {
	cin >> r >> c;
	string inp;
	for (int i = 0; i < r; i++) {
		cin >> inp;
		for (int j = 0; j < c; j++) {
			tab[i][j] = inp[j];
		}
	}
	//재귀적 dfs
	vector<bool> hist(26);
	hist[tab[0][0] - 'A'] = true;
	dfs(0, 0, hist, 1);
	cout << max_depth << endl;
}

오답코드(Stack 활용 DFS)

#include<iostream>
#include<string>
#include<stack>
#include<memory.h>

using namespace std;
int r, c;
char tab[20][20];
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
//deep copy 구현
struct candi {
	int i, j;
	bool hist[26] = {false};
	void operator=(candi s) {
		this->i = s.i;
		this->j = s.j;
		memcpy(this->hist, s.hist, sizeof this->hist);
	}
	candi() {
		memset(this->hist, 0, sizeof this->hist);
	}
};
bool inbox(int i, int j) {
	return i >= 0 && i < r&& j >= 0 && j < c;
}
int calc_len(bool hist[26]) {
	int sum = 0;
	for (int i = 0; i < 26; i++) {
		if (hist[i]) sum++;
	}
	return sum;
}
/*
void print_candi(candi c) {
	cout << "i : " << c.i << " , j : " << c.j << endl;
	for (int i = 0; i < 26; i++) {
		cout <<i<< ":" << c.hist[i] << " , ";
	}
	cout << endl<<endl;
}
*/
int main() {
	cin >> r >> c;
	string inp;
	for (int i = 0; i < r; i++) {
		cin >> inp;
		for (int j = 0; j < c; j++) {
			tab[i][j] = inp[j];
		}
	}
	stack<candi> s;

	candi cur;
	cur.i = 0;
	cur.j = 0;
	cur.hist[tab[0][0] - 'A'] = true;
	//print_candi(cur);

	s.push(cur);
	int max_len = 0;
	
	while (!s.empty()) {
		cur = s.top();
		s.pop();
		//cout << "current below \n";
		//print_candi(cur);
		for (int k = 0; k < 4; k++) {
			candi child = cur;
			child.i = cur.i + di[k];
			child.j = cur.j + dj[k];
			char child_char = tab[child.i][child.j];
			if (inbox(child.i, child.j) && child.hist[child_char - 'A'] == false) {
				child.hist[child_char - 'A'] = true;
				s.push(child);
				//print_candi(child);
			}
			else {//결산
				max_len = max(max_len, calc_len(cur.hist));
			}
		}
	}
	cout << max_len << endl;
}