[백준][1987][C++] 알파벳

링크

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

1987번: 알파벳

해설

DFS를 아신다면 간단한 문제입니다.

 

원래 이문제를 풀 때는 스택을 사용해야 하지만 딱히 경로를 저장해야 하는 문제는 아니라서

bool can_go[26];

을 이용해서 이미 지나간 알파벳인지 아닌지만 검사해서 DFS 를 실시하면 됩니다.

 

코드

#include <iostream>
using namespace std;
 
char table[20][20];
 
int R, C, MAX = 1, NOW = 1;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
 
bool can_go[26];
 
void DFS(int _x, int _y) {
 
	if (NOW > MAX)
		MAX = NOW;
	for (int i = 0; i < 4; ++i) {
		int nx = dx[i] + _x;
		int ny = dy[i] + _y;
		if (0 <= nx && nx < C && 0 <= ny && ny < R) {
			int alp = table[ny][nx] - 'A';
			if (can_go[alp]) {
				can_go[alp] = false;
				++NOW;
				DFS(nx, ny);
				--NOW;
				can_go[alp] = true;
			}
		}
	}
 
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	char in[21];
	fill_n(can_go, 26, true);
 
	cin >> R >> C;
	for (int i = 0; i < R; ++i) {
		cin >> in;
		for (int j = 0; j < C; ++j) {
			table[i][j] = in[j];
		}
	}
	can_go[table[0][0] - 'A'] = false;
	DFS(0, 0);
	cout << MAX;
	return 0;
}