BOJ 1987 - 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

 

DFS 와 Backtracking 을 혼합해서 풀어야 하는 문제였다.

DFS 로 (y, x) 지점을 방문하면서 이동할 수 있는 지역이 있으면 

이동할 수 있는 새 지역 (ny, nx) 에 대해서 DFS 를 수행해준다

그리고 DFS 가 끝나는 때에 다시 초기 상태로 돌려놓는 백트래킹을 수행한다.

최대한으로 이동할 수 있는 칸의 수를 찾아내야 하므로

DFS 를 돌릴 때, y, x 좌표 뿐 아니라, cnt 라는 변수 하나 더 넣어서 몇번 이동했는지 계산한다

그리고 그 중 가장 큰 값을 답으로 정한다.

 

 

- c++

 

#include <algorithm>
#include <iostream>
 
using namespace std;
 
int r, c, answer;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
bool alphabet[26];
bool visited[21][21];
char adj[21][21];
 
void dfs(int y, int x, int cnt) {
    answer = max(answer, cnt);
    visited[y][x] = true;
    alphabet[adj[y][x] - 'A'] = true;
 
    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;
        if (!visited[ny][nx] && !alphabet[adj[ny][nx] - 'A']) {
            dfs(ny, nx, cnt + 1);
        }
    }
 
    alphabet[adj[y][x] - 'A'] = false;
    visited[y][x] = false;
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> r >> c;
 
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            cin >> adj[i][j];
 
    dfs(1, 1, 1);
    cout << answer;
 
    return 0;
}