[백준] 1987-알파벳(C++)

문제링크:https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

전형적인 dfs 문제입니다. 수의 범위도 20까지 이기때문에 무조건 dfs 구현이구나 생각했습니다.

 

생각보다 쉽게 문제를 풀어 의아했습니다. 별다른 가지치기를 하지 않고 ac를 받았기 때문입니다. 

 

#include <iostream>
#include <string>
using namespace std;
int result = 0;
bool al[26] = { 0 };
int x_ar[4] = { 0,0,1,-1 };
int y_ar[4] = { 1,-1,0,0 };
int r = 0, c = 0;
string arr[20];
void dfs(int yy,int xx,int cnt) {
	if (cnt > result) { 
		result = cnt; 
	}

	for (int i = 0; i < 4; i++) {
		int y = y_ar[i] + yy;
		int x = x_ar[i] + xx;
		if (y >= 0 && y < r && x >= 0 && x < c) {
			if (al[arr[y][x] - 65] == 0) {
				al[arr[y][x] - 65] = 1;
				dfs(y, x, cnt + 1);
				al[arr[y][x] - 65] = 0;
			}
		}
	}
	return;

}

int main(){
	cin >> r >> c;
	for (int i = 0; i < r; i++)
		cin >> arr[i];
	
	
	al[arr[0][0] - 65] = 1;
	dfs(0, 0, 1);
	al[arr[0][0] - 65] = 0;
			
	
	cout << result << endl;
}

 

왜 백트래킹에 들어가는지 아직도 잘 모르겠습니다...

대문자 A가 아스킷 코드값으로 65이기 때문에 아래와 같이 마킹을 해주었습니다.

 

화이팅!!