BOJ 1987 : 알파벳

풀이 요약

DFS

풀이 상세

1. 좌표에서 움직이면서 지금까지 지나쳐온 알파벳은 이동하지 않을 때 이동할 수 있는 최댓값을 찾아야한다.

2. DFS 로 이동을 하며 이동할 수 있는 최대를 움직인 후, 이후 방문처리를 해제하여 다른 경우의 수에도 진행시에도 돌아본다.

정답코드

#include <iostream>
#include <vector>
using namespace std;
int R, C, ans, visited[100],dr[4] = {-1, 0, 1, 0}, dc[4] = {0, -1, 0, 1};
vector<string> a;

void input() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> R >> C;
    string str;
    for (int i = 0; i < R; i++) {
        cin >> str;
        a.push_back(str);
    }
}

void solve(int r, int c, int dist) {
    visited[a[r][c]]++;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (visited[a[nr][nc]]) continue;
        solve(nr, nc, dist + 1);
    }
    visited[a[r][c]]--;
    ans = max(ans, dist);
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve(0, 0, 1);
    output();
}