[백준/c++] - 1987 알파벳

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

1987번: 알파벳

 

 

 

 

 

 

 처음에는 그래프 문제같아서 BFS로 접근해볼까 했다. 근데 잠깐 생각해보니 어느 지점에 대한 최단 경로를 구하는 것이 아니라서 아 이건 DFS로 풀면 되겠다 라는 생각까진 떠올렸는데 DFS가 익숙치 않아서 정답코드를 보고 참고해서 다시 풀게 되었다.

 

 

 

 

 

 

 DFS로 풀면되서 특별하게 어려운 문제는 아니지만 보통 DFS로 풀 수 있는 문제는 BFS로도 풀 수 있다고 생각했었는데 그렇지 않은 문제도 있어서 또 깨달음을 얻게 된 문제. BFS로 이 문제를 풀려고 하면 자신이 지나온 길을 체크하기에도 쉽지 않고, 최대한 많이 이동을 해야하는데 BFS는 퍼져 나가면서 최단 이동 횟수를 기록하는 방식이라 문제의 방향성 과도 맞지 않는다.

 

 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
#include <stack>

using namespace std;

// DFS 문제, 재귀형


struct Pos {
	int X;
	int Y;
};

int frontX[4]{ 1, -1, 0, 0 };
int frontY[4]{ 0, 0, 1, -1 };

vector<vector<char>> map;
int ans = 0;
bool alpha[26]{ false, };

int R, C;

void input() {
	cin >> R >> C;

	map.resize(R);

	for (int i = 0; i < R; i++) {

		map[i].resize(C);

		for (int j = 0; j < C; j++) {
			char c;
			cin >> c;
			map[i][j] = c;
		}
	}

}

void dfs(Pos pos, int goCount) {

	bool canGo = false;

	if (alpha[map[pos.Y][pos.X] - 'A'] == false) { // 시작 지점 알파벳 방문 처리
		alpha[map[pos.Y][pos.X] - 'A'] = true;
	}

	for (int i = 0; i < 4; i++) {

		Pos nextPos{ pos.X + frontX[i], pos.Y + frontY[i] };

		// 맵 벗어낫는지 체크
		if (nextPos.X >= C || nextPos.Y >= R || nextPos.X < 0 || nextPos.Y < 0) continue;


		// 알파벳 겹치는지 체크
		if (alpha[map[nextPos.Y][nextPos.X] - 'A']) continue;


		// 방문 시도
		canGo = true;

		alpha[map[nextPos.Y][nextPos.X] - 'A'] = true;
		dfs(nextPos, goCount + 1);
		alpha[map[nextPos.Y][nextPos.X] - 'A'] = false; // 재방문 할 수 있도록 초기화

	}

	if (canGo == false) { // 더 갈 수 없다면 정산
		ans = max(ans, goCount);
		return;
	}

}


int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	input();
	dfs(Pos{ 0, 0 }, 1);

	cout << ans << endl;

}

 

 

 

 

 

 재귀 방식으로 구현한 DFS 코드를 참고했다. 보통의 DFS 문제라면 목적지 도달을 체크하지만 이 문제에서는 더 이상 이동 불가능 할때에만 DFS가 종료된다. 

 

 

 

 

 

 

 

 인터넷의 다른 정답 코드를 참고했는데 특이했던건 지나온 알파벳의 기록을 size가 26인 배열에 하였다는 점이 독특했다. 원래는 vector에 넣어서 find 함수로 일일이 체크했는데 이 방법이 훨씬 효율적인것 같다.