BOJ : 1987 알파벳

---

[BOJ 1987(G4) 리뷰]

 

후... 엄청나게 힘들었던 문제다.

처음엔 문제 잘못읽고 BFS로 접근했다. 코딩 다했는데 그제서야 문제 제대로 이해하고 싹 갈아엎었다.

처음엔 set을 통해 문자를 하나하나씩 쌓으면서 중복된게 있는지 비교했는데, 처음에 백트래킹하면서 쌓아놓았던 문자를 제거하지 않아서 틀렸다. 이걸 수정하고 제출했더니 set때문인지 시간초과가 나왔다.

그래서 인터넷을 참고해 중복된걸 확인하는것을 A~Z까지 배열에 담아 O(1)로 확인했더니 통과되었다.

 

후.. 2시간은 넘게 걸린거같다.

 

---

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


char board[21][21];
bool isUsed[21][21];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int maxcnt = 0;
bool visit[27];
int n, m;
string s;

void func(int cur, int r, int c) //r,c 는 좌효 cur은 현재까지 지나온 칸의 개수
{
	if (visit[board[r][c]-'A']) return; //해당문자가 set내에 존재하면 return
	visit[board[r][c] - 'A'] = 1;
	
	maxcnt = max(maxcnt, cur);
	for (int dir = 0; dir < 4; dir++)
	{
		int nx = r + dx[dir];
		int ny = c + dy[dir];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		if (isUsed[nx][ny]) continue;
		isUsed[nx][ny] = 1;
		func(cur + 1, nx, ny);
		isUsed[nx][ny] = 0;
	}
	visit[board[r][c] - 'A'] = 0;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cin >> board[i][j];
	}

	isUsed[0][0] = 1; //1방문처리하고 1부터 탐색
	func(1, 0, 0);
	
	cout << maxcnt;


}