(백준/c++) 1987 - 알파벳/ DFS, 백트래킹

 

" (백준/c++) 1987 - 알파벳/ DFS, 백트래킹"

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

---

🏆 solved.ac 난이도: 골드4

 

BFS로 풀었다가 ~ DFS와 Set을 함께해서 풀었다가 시간초과로 막혀서 Set을 없애고 문제를 풀었다.. 

🔸 BFS로 풀었을 때 나왔던 이슈 

- BFS는 넓이 우선으로 빨간색으로 체크한 부분이 이전 파란색 Que에 [F]가 담겨  파란색[E] 주변 노란색[H] [F]을 담으려 할 때 [F]가 빠지게 된다. 

 

 

🔸 DFS + Set 풀이 

Set으로 find해서 지나간 경로에 현재 알파벳이 포함되었는지 확인하려고했다.

• Set의 find 시간복잡도는 O(logN)
• 배열은 바로 접근 가능하기 때문에 O(1)

set<char> alphabets;
alphabets.find(Arr[next_x][next_y]) == alphabets.end()

 

🔸 확인할 부분

시작하는 구간에서 alphabet 정보와 방문 정보를 모두 false이켜준다. 첫 시작 부분에 서 (1, 0), (0, 1) 만 pCount에들어오게 될거다. 

위 코드를 보면 for (int i = 0; i < 4; ++i) 를 빠져나가면 현재 방문을 false 시켜준당

 

최종코드

#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;

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

char Arr[21][21]; 
bool visited[21][21] = { false,  }; 
queue<pair<int, int>> que; 
bool alphabets[26] = {false, };
int R, C; 
int Results = 0;

int AlphabetToNum(char pChr)
{
	return pChr - 'A';
}

void DFS(int x, int y, int pCount)
{
	alphabets[AlphabetToNum(Arr[x][y])] = true;
	for (int i = 0; i < 4; ++i)
	{
		int next_x = dx[i] + x;
		int next_y = dy[i] + y;

		if (pCount == 0)
		{
			memset(alphabets, false, sizeof(alphabets));
			alphabets[AlphabetToNum(Arr[x][y])] = true;
			memset(visited, false, sizeof(visited));
			visited[x][y] = true;
		}

		if (alphabets[AlphabetToNum(Arr[next_x][next_y])] == false
			&& next_x >= 0 && next_x < R && next_y >= 0 && next_y < C
			&& visited[next_x][next_y] == false)
		{
			visited[next_x][next_y] = true;
			DFS(next_x, next_y, pCount + 1);
		}

		if (Results < pCount)
		{
			Results = pCount;
		}
	}
	visited[x][y] = false; 
	alphabets[AlphabetToNum(Arr[x][y])] = false;
}

int main(void)
{

	cin >> R >> C; 

	for (int i = 0; i < R; ++i)
	{
		for (int j = 0; j < C; ++j)
		{
			char chr;
			cin >> chr;
			Arr[i][j] = chr;
		}
	}

	DFS(0, 0, 0);
    
	cout << Results + 1;
	return 0;
}