[1987] 알파벳

• 입력: 세로 r 가로 c r*c로 된 대문자 집합
• 출력: 상하좌우로 움직이면서 방문했던 알파벳은 방문하지 않았을 때 최대의 길이
• 알고리즘: DFS, 백트래킹
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <string> #include <cstdio> using namespace std; void DFS(int, int, int, int&); int r, c; vector<string> board; vector<bool> alphabet(26, false); int main() { scanf("%d%d", &r, &c); board = vector<string>(r); for (int i = 0; i < r; i++) cin >> board[i]; int max = 0; DFS(0, 0, 1, max); printf("%d\n", max); return 0; } void DFS(int x, int y, int d, int& m) { alphabet[board[x][y] - 'A'] = true; if (m < d) m = d; if (x + 1 < r && !alphabet[board[x + 1][y] - 'A']) DFS(x + 1, y, d + 1, m); if (y + 1 < c && !alphabet[board[x][y + 1] - 'A']) DFS(x, y + 1, d + 1, m); if (x - 1 >= 0 && !alphabet[board[x - 1][y] - 'A']) DFS(x - 1, y, d + 1, m); if (y - 1 >= 0 && !alphabet[board[x][y - 1] - 'A']) DFS(x, y - 1, d + 1, m); alphabet[board[x][y] - 'A'] = false; }

• 문제 참고: https://www.acmicpc.net/problem/1987