알파벳

백준 1987번: 알파벳

아이디어

상하좌우 알파벳중에 고른 적 없는 알파벳이 있으면 고르고, 함수가 끝나면 방문 배열에서 방문한 적 없다고 표시해준다.

코드

#include <bits/stdc++.h>

using namespace std;
int R, C, MAX = 0;
char arr[20][20];
bool visited[26];
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};

void solve(int y, int x, int cnt) {
    MAX = max(MAX, cnt);
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= R || nx >= C || ny < 0 || nx < 0) continue;
        if (visited[arr[ny][nx] - 'A']) continue;
        visited[arr[ny][nx] - 'A'] = true;
        solve(ny, nx, cnt+1);
        visited[arr[ny][nx] - 'A'] = false;
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
        }
    }
    visited[arr[0][0] - 'A'] = true;
    solve(0, 0, 1);
    cout << MAX;
    return 0;
}

여담

맨 처음 알파벳은 항상 방문처리 되어있음에 유의. 따라서 count도 1부터 시작한다.