[c++/백준] 1987번: 알파벳*

문제 링크

1987번: 알파벳

풀이

DFS와 백트래킹으로 푸는 문제
처음에는 시간초과가 나길래 뭐지.. 싶었는데, set으로 풀었던 것과 매개변수로 넣을 배열 복사하는 과정에서 시간초과가 난 것 같음. 다음부터는 재귀 호출 하고 다시 배열을 원래대로 돌려놓는 식으로 풀어야겠다.

1. 알파벳 체크하는 건 아스키 코드를 이용한다.
2. DFS함수를 호출하는데, 상하좌우를 봐가면서 범위 내이고, 지나가지 않은 알파벳일 경우 계속 진행한다. 원래 visit 넣어줘야 하지만, 한 번 지나갔던 곳은 알파벳만으로 체크가 되기 때문에 빼도 된다.
   2-1. 현재 위치의 알파벳 체크해주고 재귀호출, 그리고 다시 원래대로 되돌려놔야 다른 방향에서 진입할 때 방문했다고 안 지나가는 일이 없게 할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int r, c;
vector<vector<char>> v;

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

int alpha[26];

int answer=0;

void DFS(int y, int x, int dist)
{
	answer = max(answer, dist);
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
		if (alpha[(int)v[ny][nx] - 65]==1) continue;

		alpha[(int)v[ny][nx] - 65] = 1;
		DFS(ny, nx, dist+1);
		alpha[(int)v[ny][nx] - 65] = 0;
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> r >> c;
	v.resize(r, vector<char>(c));
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> v[i][j];
		}
	}

	alpha[(int)v[0][0] - 65] = 1;
	DFS(0, 0, 1);

	cout << answer << endl;

}