[알고리즘 문제] 백준1987 - 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

전형적인 dfs문제 입니다. 알파벳을 체크와 이미 방문한 곳인지를 검사하면서 탐색하고 이동할때마다 max값을 갱신해주는 방법을 사용하였습니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int ans = -1;
int width, height;

char arr[21][21];
int visited[21][21];
int check[91];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

void dfs(int y, int x, int depth)
{
    ans = max(depth, ans);

    for (int i = 0; i < 4; i++)
    {
        int newX = x + dx[i];
        int newY = y + dy[i];

        if (newX < 0 || newY < 0 || newX >= width || newY >= height)
        {
            continue;
        }
        if (!check[arr[newY][newX]] && !visited[newY][newX])
        {
            check[arr[newY][newX]] = 1;
            visited[newY][newX] = 1;
            dfs(newY, newX, depth + 1);
            visited[newY][newX] = 0;
            check[arr[newY][newX]] = 0;
        }
    }
}

int main()
{

    cin >> height >> width;

    for (int y = 0; y < height; y++)
    {
        string s;
        cin >> s;
        for (int x = 0; x < s.size(); x++)
        {
            arr[y][x] = s[x];
        }
    }

    check[arr[0][0]] = 1;
    visited[0][0] = 1;

    dfs(0, 0, 1);
    cout << ans << endl;
    return 0;
}