알파벳 (feat. 백준, 1987번)

알파벳
https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
char arr[21][21];
int R, C, ans, dx[4], dy[4];
bool check['Z' - 'A' + 1];
void dfs(register int x, register int y, register int cnt){
    for(register int d = 0, nx, ny; d < 4; ++d){
        nx = x + dx[d], ny = y + dy[d];
        if(1 <= nx && nx <= R && 1 <= ny && ny <= C)
            if(!check[arr[nx][ny] - 'A']){
                check[arr[nx][ny] - 'A'] = true;
                dfs(nx, ny, cnt + 1);
                check[arr[nx][ny] - 'A'] = false;
            }
    }
    ans = max(ans, cnt);
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    ans = 0;
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    memset(check, false, sizeof(check));
    cin >> R >> C;
    for(register int r = 1, c; r <= R; ++r)
        for(c = 1; c <= C; ++c)
            cin >> arr[r][c];
    check[arr[1][1] - 'A'] = true;
    dfs(1, 1, 0);
    cout << ans + 1;
    return 0;
}
// *&)*@*

 

1. 전형적인 dfs 문제입니다.
2. 깊이 우선 탐색으로 모든 조건에 대해서 가장 많이 이동한 숫자가 답이 됩니다.