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

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

1987번: 알파벳

DFS와 되추적 기법

(1,1)에서 시작되는 노드를 따라 갔던 정점 빼고 가장 많은 정점의 수를 출력해야한다.

즉, (1,1)에서 시작하여 모든 노드를 방문하며 - > DFS / BFS

모든 경우의 수를 생각해야한다 -> 되추적 기법

 

모든 경우의 수를 생각해야하는 거면 DP도 되지 않나라는 생각을 했는데

2차원 배열이 사용되는 그런 길? 타일 같은 공간이 필요하면 되추적으로 하는 것 같다(..)

 

되추적 잘 몰라서 전에 풀었던 N-Queen을 한 삼천번 들여다보면서 되추적이 뭔지 어떻게 사용하는지 생각해보고 풀었다.

유망하지 않음을 판단하고 가지치기를 하는 것 되추적 기법인데 

솔직히 아직까진 남의 소스를 보고 나서야 스스로 짤 수 있지 

잘 모르겠다.. 어떻게 짜는 건지 감이 안 온다 ㅠ 

 

 

잘못된 정보 미쳤다. 

---

 

위 처럼 적혀있어서 2024. 6. 17 에 다시 풀었습니다. 

대 2학년?? 과거의 나 .. DFS도 많이 힘들어 했었구나...

 

🖍 풀이

 

문제에서 출발점도 정답에 포함하라고 하는 것에 유의하자. 

또한 입력이 char로 오는데 이래서 visited 방문 처리를 위해서 map, set을 썼던 과거의 코드를 보았다. 

하지만 이럴 필요가 없다. 문제에서 주어지는 char는 모두 대문자다. 

아래의 연산으로 char를 int처럼 다뤄보자.

 

board[i][j] -'A'

 

 

혹시나 첨언하자면! 

BFS는 사방의 모든 경로에 대해 알파벳 체크를 하기 때문에 적합하지 않다. 

 

💾  소스

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

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

int R, C, answer = 0;
vector<vector<char> > board;
bool visited[21] = {false, };

void dfs(const int _x, const int _y, const int sum)
{
    answer = (answer > sum ? answer : sum);
    for (int d = 0; d < 4; ++d)
    {
        int x = _x + dx[d];
        int y = _y + dy[d];

        if (x < 0 || y < 0 || x >= R || y >= C ||
            visited[board[x][y]-'A'])

            continue;
        visited[board[x][y] -'A'] = true;
        dfs(x, y, sum + 1);
        visited[board[x][y]-'A'] = false;
    }
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    cin >> R >> C;

    board.resize(R, vector<char>(C));
    for(int i=0; i<R; ++i)
        for(int j=0; j<C; ++j)
            cin >> board[i][j];

    visited[board[0][0]-'A'] = true;
    dfs(0, 0, 1);

    cout << answer;

    return 0;
}