🖊️ 문제

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

---

🖊️ 풀이

그냥 DFS로 푸는 문제인데,
unordered_set을 이용해서 풀려고 하니 시간초과가 났다.

아무래도 unordered_set의 삽입, 삭제, find에서 시간복잡도를 잡아먹기 때문인 것 같다.

unordered_set은 최악의 경우 O(N)까지 내려갈 수 있기 때문에, 배열을 이용하자!

전체 알파벳만 체크해주면 되므로, 일차원배열을 사용해서 시간복잡도를 O(1)으로 줄이자.

틀린 풀이

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int R, C;
char arr[21][21];
bool visited[21][21] = { false, };
unordered_set<char> us;
int result = 0;

void DFS(int x, int y, int cnt)
{
	result = max(result, cnt);
	cout << x << " " << y <<  " : "  << cnt << endl;
	if (x == R && y == C) {
		return;
	}
	if (x + 1 <= R && us.find(arr[x + 1][y]) == us.end()) {
		us.insert(arr[x + 1][y]);
		DFS(x + 1, y, cnt + 1);
		us.erase(arr[x + 1][y]);
	}
	if (x - 1 >= 1 && us.find(arr[x - 1][y]) == us.end()) {
		us.insert(arr[x - 1][y]);
		DFS(x - 1, y, cnt + 1);
		us.erase(arr[x - 1][y]);
	}
	if (y + 1 <= R && us.find(arr[x][y + 1]) == us.end()) {
		us.insert(arr[x][y + 1]);
		DFS(x, y + 1, cnt + 1);
		us.erase(arr[x][y + 1]);
	}
	if (y - 1 >= 1 && us.find(arr[x][y - 1]) == us.end()) {
		us.insert(arr[x][y - 1]);
		DFS(x, y - 1, cnt + 1);
		us.erase(arr[x][y - 1]);
	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	cin >> R >> C;

	string input;
	for (int i = 1; i <= R; i++) {
		cin >> input;
		for (int j = 0; j < C; j++) {
			arr[i][j + 1] = input[j];
		}
	}

	us.insert(arr[1][1]);
	DFS(1, 1, 1);

	cout << result << endl;
}

풀이

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

int R, C;
char arr[21][21];
bool visited[26] = { false, };
int result = 0;
int dir[2][4] = { {-1, 1, 0, 0}, {0, 0, -1, 1} };

void DFS(int x, int y, int cnt)
{
	result = max(result, cnt);

	for (int i = 0; i < 4; i++) {
		int nextX = x + dir[0][i];
		int nextY = y + dir[1][i];

		if (nextX < 1 || nextY < 1 || nextX > R || nextY > C) continue;
		if (visited[arr[nextX][nextY] - 'A']) continue;
		visited[arr[nextX][nextY] - 'A'] = true;
		DFS(nextX, nextY, cnt + 1);
		visited[arr[nextX][nextY] - 'A'] = false;
	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	cin >> R >> C;

	string input;
	for (int i = 1; i <= R; i++) {
		cin >> input;
		for (int j = 0; j < C; j++) {
			arr[i][j + 1] = input[j];
		}
	}

	visited[arr[1][1] - 'A'] = true;
	DFS(1, 1, 1);

	cout << result << endl;
}

4가지 방향 탐색 시 배열을 이용해서 수정해야 하는 코드를 줄이는 방향으로 하자!