[BOJ알고리즘, C++]#1987_알파벳, 그래프, DFS, 백트래킹

 

#1. 문제

 

1987번: 알파벳

 

---

 

#2. 풀이

 

1. 그래프

 

[자료구조]#6_그래프

 

그래프 자료구조는 노드와 간선의 집합으로 이루어진 비 선형 자료구조입니다. 그래프 자료구조에서 노드 간 연결 관계는 간선으로 표현하며, 간선의 방향성, 연결 강도에 따라서 다양한 형태의 그래프를 표현할 수 있습니다.

 

2. DFS, 깊이 우선 탐색

 

[자료구조]#6_그래프

 

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지 우선적으로 탐색하는 방법입니다. DFS는 일반적으로 재귀 호출 혹은 스택 자료구조를 통해 구현 가능합니다. 

 

3. 백트래킹

 

[알고리즘]#6_백 트래킹

 

백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며, 현재 선택한 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 단계로 돌아가 다른 경로에 대한 탐색을 시도하는 방법입니다. 대표적인 백트래킹 알고리즘 활용처는 미로 찾기, 순열, 조합, N-Queen 문제, 그리고 그래프 탐색 경로 찾기 문제 등이 있습니다.

 

4. 이 문제의 백트래킹은 재귀 호출 DFS와 방문 여부 초기화의 조합!

 

1. 전형적인 미로 찾기 유형의 문제입니다. 하지만, 단순한 DFS를 수행하면 시간 초과 등의 오류가 발생합니다. 따라서, 백트래킹을 통해 DFS를 최적화합니다.
2. 백트래킹은 현재 정점에서 다음 경로 후보에 대한 DFS를 수행하고, 현재 정점의 방문 여부를 초기화해줍니다. 이를 통해, 다음 경로 후보에서 그다음 후보 경로에 대한 탐색을 중지했을 경우, 현재 정점으로 돌아와 다음 후보 경로에 대한 탐색을 진행할 수 있습니다!
3. DFS를 수행하며, 최대 알파벳 길이 카운트를 해주어, 결과를 출력합니다.

 

---

 

#3. 코드

 

/*
    @문제 : 0X0 칸에서 시작해 각 칸에 위치한 알파벳의 중복이 없이 가능한 가장 깊은 탐색 거리
    @설명 : DFS와 백트래킹 활용
*/

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

typedef pair<int, int> p;

int R, C, ans = INT_MIN;
vector<string> adjMatrix;
vector<vector<bool>> visited;
vector<bool> alphabet(26, false);
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};

void dfs(p cPos, int cnt)
{
    int cy = cPos.first;
    int cx = cPos.second;

    ans = max(ans, cnt);
    visited[cy][cx] = true;
    alphabet[adjMatrix[cy][cx] - 'A'] = true;

    // #3. 상하좌우 인접 칸들에 대하여 dfs 수행
    for (int i = 0; i < 4; ++i)
    {
        int ny = cy + dy[i];
        int nx = cx + dx[i];

        if (ny < 0 || ny >= R || nx < 0 || nx >= C || visited[ny][nx] || alphabet[adjMatrix[ny][nx] - 'A'])
            continue;

        dfs({ny, nx}, cnt + 1);

        // #3. 백트래킹
        visited[ny][nx] = false;
        alphabet[adjMatrix[ny][nx] - 'A'] = false;
    }
}

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

    cin >> R >> C;

    adjMatrix.resize(R);
    visited.resize(R, vector<bool>(C, false));

    for (int i = 0; i < R; ++i)
    {
        cin >> adjMatrix[i];
    }

    // #1. 0x0 칸부터 dfs를 수행합니다.
    dfs({0, 0}, 1);

    cout << ans;

    return 0;
}

 

---