[백준 1987] - 알파벳(C++)

📕문제

---

세로 R 칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

📕입력

---

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R, C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

📕출력

---

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

🔎문제 해석

---

항상 이런 탐색 문제는 BFS로 하는지 DFS로 하는지 초반에 가닥을 잡는 것이 중요하다.

문제를 읽어보면 항상 답이 나온다.

문제에서 최대로 진행할 수 있는 칸을 구하라는 말이 있다. 즉 이말은 DFS로 푸는 것이 효율적이라고 할 수 있다.

어떠한 경로로 갔다가 막히면 그 출발점에서 다시 다른 경로를 선택해야 하기에 모든 방향을 탐색하는 것보단 하나의 선택지로 쭉 탐색한 뒤 실패하면 다시 제자리로 돌아가서 다른 경로를 탐색하는 것이 맞다고 생각했다.

(실제로 맞는지는 차차 확인하면 될거같은..~)

 

📃풀이 방식

---

1. 크게 사용한 배열은 3가지이다.
   1. graph : 입력한 문자를 저장하는 배열
   2. visit : 방문여부를 check
   3. alph : 해당 알파벳을 밟았는지를 check 
      
      1. 대문자 A는 아스키코드 값이 65라서 A를 배열의 인덱스 0으로 잡고 65를 뺀 index 값으로 넣어줫음.
2. 출발점을 푸쉬하고 DFS 실행
3. DFS
   1. 내가 지나온 칸의 길이를 항상 갱신 (DFS깊이와 , 이미 저장된 값)
   2. stack에 top에 있는 좌표를 추출하고 pop하고, 해당 좌표를 방문처리, 알파벳 방문 처리
   3. 상하좌우로 탐색
      1. 이동한 좌표가 배열을 벗어난다면 pass
      2. 만약 이동한 좌표에 해당하는 알파벳을 밟았거나, 이동한 좌표를 이미 방문했다면 pass
   4. 탐색 후에 적절한 좌표라면 알파벳과 방문을 처리하고 stack에 push하고 DFS를 재귀호출
   5. 만약 재귀호출이 끝나면 그 차례에 방문했던 좌표를 방문처리를 제거한다. (알파벳,방문처리)
4. DFS가 끝나면 result(최대로 진행한 칸수)를 출력한다.

💻코드

/*
골드4 1987 알파벳
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int r, c;
vector<vector<char>> graph;
vector<vector<int>> visit;
vector<int> alph(26, 0);
vector<int> x = {1, -1, 0, 0};
vector<int> y = {0, 0, 1, -1};
stack<pair<int, int>> s;
int C = 1, result = 0;
void dfs(int count);
int main()
{
    cin >> r >> c;
    graph.resize(r, vector<char>(c, 0)); //입력행렬
    visit.resize(r, vector<int>(c, 0)); //방문행렬
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> graph[i][j];
        }
    }
    s.push(make_pair(0, 0)); //출발점
    dfs(C); 
    cout << result; //최대값 출력하기
}
void dfs(int count)
{
    result = max(result, count); //최대값 계속해서 갱신
    while (!s.empty()) 
    {
        int fx = s.top().first;
        int fy = s.top().second;
        s.pop();
        visit[fx][fy] = 1;            //현재 지점 방문처리
        alph[graph[fx][fy] - 65] = 1; //현재 지점 방문처리

        for (int i = 0; i < 4; i++)
        {
            int mx = fx + x[i];
            int my = fy + y[i];
            if (mx < 0 || my < 0 || mx >= r || my >= c) //적절하지 않은 이동
            {
                continue;
            }
            if (alph[graph[mx][my] - 65] == 1 || visit[mx][my] == 1) //한번 방문한 알파벳이거나, 이미 방문한 지역이라면
            {
                continue;
            }
            alph[graph[mx][my] - 65] = 1; //방문한곳 알파벳 기록
            s.push(make_pair(mx, my)); //stack에 push
            dfs(count + 1);
            //dfs 빠져나왓다면 다시 초기화 시켜주기
            visit[mx][my] = 0;            //이동시킨점 다시 되돌리기
            alph[graph[mx][my] - 65] = 0; //이동시킨점 다시 되돌리기.
        }
    }
}

✔느낀 점

• 우선 이 문제 굉장히 빨리 풀어서 뿌듯했지만, 그냥 골드 4의 난이도라고 하기에는 조금 애매했던 것 같다.
• dfs의 구조와 알파벳의 여부를 체크하는 방법만 알면 빨리 풀 수 있는 문제인 것 같다.
• 나는 10분 만에 풀었음!!