[BOJ] 백준 1987 알파벳 c++ (dfs, 백트래킹, 그래프)

문제 출처 : https://www.acmicpc.net/problem/1987

1987번: 알파벳

풀이

dfs를 사용하여 해결한 문제이다.

 

그래프 문제에서 자주 쓰는 dx, dy 배열을 선언해 4방향 탐색을 돌려주면 된다.

 

여기서 주의할 점이 다음 dfs를 호출할때 cnt + 1, cnt++, ++cnt 에 따라 결과값이 달라진다는 것에 유의하자.

dfs(row + dy[i], col + dx[i], cnt + 1);

---

코드

#include <iostream>
#include <algorithm>

using namespace std;

int R, C, ans;
char arr[20 + 2][20 + 2];
bool check[26];

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

void dfs(int row, int col, int cnt){
	ans = max(ans, cnt);

	for(int i = 0; i < 4; i++){
		int ny = row + dy[i];
		int nx = col + dx[i];
		
		if(ny == 0 || ny > R || nx == 0 || nx > C) continue;

		if(!check[arr[ny][nx] - 'A']){
			check[arr[ny][nx] - 'A'] = true;
			dfs(row + dy[i], col + dx[i], cnt + 1);
			check[arr[ny][nx] - 'A'] = false;
		}
	}

	return;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(NULL);

	cin >> R >> C;
	for(int i = 1; i <= R; i++)
		for(int j = 1; j <= C; j++)
			cin >> arr[i][j];

	check[arr[1][1] - 'A'] = true;
	dfs(1, 1, 1);
	cout << ans;

	return 0;
}