[백준] 1987번 알파벳

문제

https://www.acmicpc.net/problem/1987

풀이과정

입력으로 알파벳 대문자로 이루어진 보드판이 주어진다.

(0,0) 부터 문제에서 주어진 규칙에 따라 인접한 상하좌우로 이동할 수 있는 최대칸 수를 출력해야하는 문제다.

DFS로 접근을 했고 처음에는 문제를 잘못보고 이전 알파벳하고 방문하는 알파벳만 다르면 방문할 수 있는 줄 알았다.

문제를 자세히 보면 밟아온 보드판에서 사용된 알파벳은 다시 밟을 수 없다고 한다.

그래서 알파벳의 사용여부를 체크하는 배열을 만들어 DFS를 돌렸다.

소스코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define MAX 21

int r, c;
char alpha[MAX][MAX]; // 입력되는 보드판
bool chk_alpha[26]; // 사용된 알파벳 
int dx[4] = { 0, 0,-1,1 };
int dy[4] = { -1,1,0,0 };


int DFS(int x, int y,int chk)
{
    // 사용한 알파벳 체크
    chk_alpha[chk-'A'] = true;

    int ans = 0;
    for (int k = 0; k < 4; k++)
    {
        int nx = x + dx[k]; int ny = y + dy[k];

        if (0 <= nx && nx < r && 0 <= ny && ny < c)
        {
            int next = alpha[nx][ny];
            // 다른 알파벳을 가진 판이면 방문한다.
            if (chk_alpha[next-'A']==false)
            {
                chk_alpha[next - 'A'] = true;
                // 최대값만 저장
                ans = max(ans,DFS(nx, ny,next));
                // 백트래킹
                chk_alpha[next - 'A'] = false;
            }
        }
    }

    return ans+1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> r >> c;

    for (int i = 0; i < r; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < s.length(); j++)
        {
            alpha[i][j] = s[j];
        }
    }
    cout << DFS(0, 0,alpha[0][0]) << "\n";

    return 0;
}