[c++] 백준 1987, 알파벳

백준 1987

🌲 문제 요약

보드 위의 말은 같은 알파벳이 적힌 칸을 두 번 지날 수 없다고 할 때, 좌측 상단부터 시작한 말이 최대 몇 칸을 지날 수 있는지 구하는 문제.

🌲 문제 풀이

방문한 알파벳의 정보를 담는 배열 visited에 시작 위치 알파벳을 저장한 뒤, go 함수를 호출하여 문제를 해결한다.
go 함수는 배열 a를 탐색하며, 만약 다음 이동할 위치에 놓인 알파벳이 방문하지 않은 알파벳이라면 visited[now]에 1을 저장한 이후 go 함수를 재귀적으로 호출하며, 호출이 완료된 이후에는 visited[now]의 값을 0으로 돌려놓는다.
매 호출마다 ret과 cnt 중, 더 큰 수를 ret에 저장한다.

🌲 주의

아스키코드에서 대문자 A는 10진수 65를 가리키므로, 함수 go에서 다음 이동할 위치에 놓인 알파벳을 나타내는 변수 now는 a[ny][nx] - 65의 값을 갖는다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int r, c, ret, visited[30];
char a[25][25];

void go(int y, int x, int cnt) {
	ret = max(ret, cnt);
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
		int now = a[ny][nx] - 65;
		if (!visited[now]) {
			visited[now] = 1;
			go(ny, nx, cnt + 1);
			visited[now] = 0;
		}
	}
	return;
}

int main() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> a[i][j];
		}
	}
	visited[a[0][0] - 65] = 1;
	go(0, 0, 1);
	cout << ret << '\n';
	
	return 0;
}