BOJ 1987 | 알파벳

Class 5 문제들 순회하면서 내실을 다지려고 처음으로 고른 문제다.

고등학생 때 쿼리를 이해 못해서 못 풀었던 게 한이었는지 갑자기 쿼리에 꽂혀서 그것만 풀었던지라 DFS 문제는 오히려 생소하다.

그래도 확실히 요즘 머리 싸매고 문제 풀면서 고민하는 게 감각을 많이 되찾아주는 것 같다.

문제 읽자마자 DFS는 눈치챘고 visited[] 써서 전체 탐색 해주면 되는 것 같았다.

최대 20 * 20 배열이라니, 오랜만에 보는 아주 친절한 범위 설정이다.

아무런 부담 없이 구현해서 바로 냈더니 1트 AC다. 알고리즘을 막 시작했을 때 실버 문제나 겨우 풀던 내가 이 정도까지 성장했다는 걸 체감할 수 있는 순간이었다. 트리나 그래프는 약점이었는데... 감회가 새롭다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

int xdir[4] = {1, 0, -1, 0};
int ydir[4] = {0, 1, 0, -1};

int visited[26];
int maxdepth = 0;

char board[21][21];

int R, C;

void dfs(int x, int y, int depth){
	maxdepth = max(maxdepth, depth);
	for (int i = 0; i < 4; i++){
		if (x+xdir[i] < 0 || y+ydir[i] < 0) continue;
		if (x+xdir[i] >= R || y+ydir[i] >= C) continue;
		
		char t = board[x+xdir[i]][y+ydir[i]];
		if (!visited[t-65]){
			visited[t-65] = 1;
			dfs(x+xdir[i], y+ydir[i], depth+1);
			visited[t-65] = 0;
		}
	}
}

int main(){
	cin >> R >> C;
	cin.ignore();
		
	for (int i = 0; i < R; i++){
		string k; getline(cin, k);
		for (int j = 0; j < C; j++){
			board[i][j] = k[j];
		}
	}
	
	visited[board[0][0] - 65] = 1;
	dfs(0, 0, 1);
	
	cout << maxdepth;
	
}