[C++] 백준 1987번: 알파벳

문제

난이도 : 골드 4
백준 1987번 : 알파벳

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 20;
int R, C;
char arr[MAX + 4][MAX + 4];
int visited[MAX + 4][MAX + 4];

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

vector<char> path;
int answer;

bool Search(char c)
{
    for (char alpha : path)
    {
        if (alpha == c)
            return true;
    }

    return false;
}

void DFS(int y, int x)
{
    if (visited[y][x]) return;
    
    path.push_back(arr[y][x]);
    visited[y][x] = 1;

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

        if(ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
        if (visited[ny][nx] || Search(arr[ny][nx])) continue;

        DFS(ny, nx);
    }

    answer = max(answer, (int)path.size());
    path.pop_back();
    visited[y][x] = 0;
}

int main()
{
    cin >> R >> C;

    for (int i = 0; i < R; i++)
    {
        string input;
        cin >> input;

        for (int j = 0; j < C; j++)
        {
            arr[i][j] = input[j];
        }
    }
    
    DFS(0, 0);

    cout << answer;

    return 0;
}

설명

다른 그래프 문제와 비슷한 변수들을 선언하고 말이 최대로 갈 수 있는 거리를 구하니까 DFS를 사용했다.
DFS를 돌면서 path라는 char 타입의 벡터에 현재 말이 있는 위치의 알파벳을 담는다. 그리고 이동한 곳의 알파벳이 이미 path에 있다면 가지 않는다. 현재 말이 있는 곳에서 더 이상 움직일 수 없다면 for문을 빠져나가고 현재 말이 이동한 거리(path의 size)와 정답(answer)의 최대를 정답에 담는다. 그리고 마지막으로 이동한 곳을 이동 안한 처리를 해주기 위해 path에서 빼주고 visit 했다는 표시도 없애줌. 솔직히 최적화가 안된 코드인데 통과해서 좀 찝찝한 기분이 든다. 강의를 보고 고칠 점을 알아야겠다.

결과