[C++][백준] - 알파벳 (1987번)

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

1987번: 알파벳

🔔 문제 : 

(1<= R, C,<= 20)인 세로 R칸, 가로 C칸으로 된 보드가 있습니다.

 

이 보드에는 알파벳 대문자가 적혀져 있습니다.

 

말은 왼쪽 맨 상단에 위치해 있고, 인접한 좌우상하로 움직일 수 있습니다.

 

말은 한 번 지났던 알파벳은 못지나갑니다. 이 후 말이 최대한 몇 칸 지나갈 수 있는지 출력하면 되는 문제입니다.

(처음 말이 지나는 칸도 좌측상단 칸도 1번 지나간것으로 포함됩니다.)

---

🔔 Kick Point :

 

1. 왼쪽 상단 0,0부터 시작하여 DFS()로 지나갈 수 있는 경우의 수를 구합니다.

 

2. 알파벳은 O(1)의 시간복잡도를 두기 위하여, 이미 지나간 경우는 bool 값으로 처리해줍니다.

 

3. 가장 최대 걸은 거리를 출력해줍니다.

 

 

처음에 이 문제를 풀 때는, 알파벳을 따로 배열을 이용해 담았는데 O(n)이 추가되다 보니깐 시간초과가 났습니다.

 

따라서 알파벳은 26개밖에 안되니, 이를 이용해 O(1) 시간복잡도로 바꾸니 풀 수 있게 되었습니다.

 

---

🔔 Code :

#include <iostream>
using namespace std;

char board[20][20];
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
bool alpabet[26]; // A ~ Z1987

int r, c;
int maxDist(0);

void switchV(char ch) {
	alpabet[ch - 'A'] = !alpabet[ch - 'A'];
}

void DFS(int y, int x, int cnt) {

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

		if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
		
		// 한 번 지나간 알파벳인지 확인
		if (alpabet[board[ny][nx] - 'A']) continue;

		switchV(board[ny][nx]);
		DFS(ny, nx, cnt + 1);
		switchV(board[ny][nx]);
	}

	maxDist = maxDist < cnt ? cnt : maxDist;
}


int main() {

	// Input
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			char tmp; cin >> tmp;
			board[i][j] = tmp;
		}
	}

	// Solve
	switchV(board[0][0]);
	DFS(0,0,1);

	// Output
	cout << maxDist;
}

---