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

 

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

 

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

1987번: 알파벳

---

 

해결전략

 

백트래킹, Backtracking

---

 

 

처음 시도한 코드 - set 써서 시간초과

 

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

int r, c;
vector<vector<char>> v;
set<char> alphabet;
int answer;

void BackT(int y, int x, int cnt)
{
	answer = max(answer, cnt);

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dirY[i];
		int nx = x + dirX[i];

		if (ny < 0 || r <= ny || nx < 0 || c <= nx) continue;
		if (alphabet.find(v[ny][nx]) != alphabet.end()) continue;

		alphabet.insert(v[ny][nx]);
		BackT(ny, nx, cnt + 1);
		alphabet.erase(v[ny][nx]);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> r >> c;
	v.resize(r, vector<char>(c));
	for (int y = 0; y < r; y++) {
		for (int x = 0; x < c; x++) {
			cin >> v[y][x];
			if (y == 0 && x == 0) alphabet.insert(v[0][0]);
		}
	}

	BackT(0, 0, 1);

	cout << answer;

	return 0;
}

 

위의 코드는 시간초과가 나온다. 시간 복잡도를 줄이기 위해서 ' 알파벳 방문 체크 '를 최적화해야 한다. 

 

위의 코드에서는 set<char>를 사용하여 방문한 알파벳을 체크하고 있다. set의 find 및 insert 작업은 O(log N) 시간이 걸린다.

 

각 알파벳이 고유하기 때문에, 크기가 26인 bool 배열을 사용하여 O(1)에 방문 여부를 체크할 수 있다.

 

 

아래의 정답 코드에서는 bool alpha[26] 을 사용하여 ' 알파벳 방문 체크 '를 하였다.

---

 

정답 코드

 

#include <iostream> 
#include <vector>   
using namespace std; 

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

int r, c; // 행(r), 열(c)
vector<vector<char>> v;
bool alpha[26]; // 알파벳의 방문 여부를 저장할 배열. A부터 Z까지 총 26개.
int answer; // 정답

void BackT(int y, int x, int cnt)
{
	answer = max(answer, cnt); // 현재까지의 최대 카운트를 갱신

	for (int i = 0; i < 4; i++) // 상하좌우 
	{
		int ny = y + dirY[i]; // 다음 y 위치
		int nx = x + dirX[i]; // 다음 x 위치

		if (ny < 0 || r <= ny || nx < 0 || c <= nx) continue;
		if (alpha[v[ny][nx] - 'A'] == true) continue; // 알파벳의 방문 했다면 continue

		alpha[v[ny][nx] - 'A'] = true; // 알파벳을 방문 처리
		BackT(ny, nx, cnt + 1); 
		alpha[v[ny][nx] - 'A'] = false; // 재귀 호출이 끝난 후 방문 처리를 해제
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0); 

	cin >> r >> c; 
	v.resize(r, vector<char>(c)); 
	for (int y = 0; y < r; y++) {
		for (int x = 0; x < c; x++) {
			cin >> v[y][x]; 
			
			if (y == 0 && x == 0)
				alpha[v[0][0] - 'A'] = true; // 시작점인 (0,0) 위치의 문자를 방문 처리
		}
	}

	BackT(0, 0, 1); // 백트래킹을 시작. (0,0) 위치에서 시작하며, 카운트는 1부터 시작

	cout << answer;

	return 0;
}

 

 

 

 

---