[C++] 백준 온라인 저지 1987번 알파벳 풀이

 

DFS 문제인데... 문제 설명이 좀 더 추가되었으면 좋겠는 문제(제발 쿨병 자제 좀...)

 

---

문제의 조건

 

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

 

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

 

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

=> 여기가 정말 설명이 애매한 곳이라고 생각하는데, 차라리 프로그래머스처럼 주어진 예제들에 대해서는 한 단계씩 왜 그런 답이 도출되는지 설명을 해 줬으면 좋겠습니다. 처음엔 예제 3번의 답이 왜 10인지 이해할 수가 없어서 구글링을 해야 했습니다. 

 

A(출발점)	B	D	F
B	C	D	F

 

 위와 같은 맵이 주어졌다면 일반적인 DFS/BFS로 탐색했을 때 A에서 출발해서 밑에 있는 B에 먼저 간다면 오른쪽에 있는 B는 이미 방문한 곳으로 처리되어 더 방문하지 않고 DFS/BFS가 종료됩니다. 이 경우에 답은 2가 됩니다. 

 하지만 오른쪽 B에 먼저 간다면 뒤로 쭉쭉 탐색할 수 있습니다. 2보다 더 많은 곳을 탐색할 수 있기 때문에 이 경우가 최대값이고 정답이 되어야 합니다. 그런데 문제에는 이 부분에 대한 설명이 없잖아요. 현재 위치에서 갈 수 있는 모든 방향의 경로에 대해서 각각 길이 탐색이 이루어져야 한다는 설명이 더 있었어야 한다는 생각이 정말 많이 들었습니다. 

 위의 표와 같은 예시로 설명한 블로그 글을 보고서야 문제를 이해할 수 있었습니다. 백준이 분류별로 풀 수 있어서 좋은데 문제 설명이 너무 부족해요. 백준과 프로그래머스를 합친 어디쯤 사이트가 있었으면 좋겠네요. 

 

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

 

 

풀이 과정

 

1. DFS 함수(매개변수: 현위치, 깊이)를 준비한다. 상하좌우 방향값을 저장한 2차원 배열도 준비한다. 알파벳의 길이만큼의 bool 배열을 준비한다. 

 

2. 현재 위치에서 상하좌우 네 방향으로 탐색해야 하니까 DFS 안에 방향의 횟수만큼 4번 반복하는 반복문을 준비한다.  

 

3. 반복문으로 상하좌우를 탐색하면서 다음 위치가 방문하지 않은 위치(알파벳)라면 방문 표시를 하고 DFS 함수를 호출한다. (인자값: 다음위치, 현재깊이+1)

 방문표시를 할 때엔 배열 인덱스값과 알파벳 순서를 맞춰줄 것이기 때문에 방문표시를 할 알파벳에서 'A'를 빼준다. (alphbet-'A') 알파벳은 아스키코드로 저장되어 있기 때문에 알파벳의 시작인 대문자 A만큼 빼주면 0부터 시작한다. 

 

4. DFS 함수는 재귀호출을 반복하며 최대 깊이를 찾을 것이다. 

 

5. 재귀호출이 종료되고 나오면 재귀호출을 하기 전에 방문표시를 했던 알파벳을 방문 해제한다. 현위치 오른쪽과 아래쪽에 같은 알파벳이 있다면 아까전에는 오른쪽 방향으로 탐색하느라 아래쪽으로는 가지 않았을 것이다. 다음위치 방문표시를 해제하면 이번엔 아래쪽 방향으로 탐색할 수 있을 것이다. 

 

6. DFS가 매번 호출될 때마다 현재 정답과 매개변수로 주어지는 깊이 중 더 큰 값을 정답에 저장한다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int height, width;
vector<vector<int>> dir;
vector<vector<char>> board;
vector<bool> passed;
int answer = 0;

void dfs(pair<int, int> pos, int count)
{
    answer = max(answer, count);
    
    for (int i = 0; 4 > i; i++)
    {
        auto nextPos = make_pair(pos.first + dir[i][0], pos.second + dir[i][1]);
        if (0 > nextPos.first || height <= nextPos.first
            || 0 > nextPos.second || width <= nextPos.second)
            continue;
        
        //알파벳에서 'A'만큼 빼주면 0부터 시작하는 숫자가 된다. 
        if (!passed[board[nextPos.first][nextPos.second] - 'A'])
        {
            passed[board[nextPos.first][nextPos.second] - 'A'] = true;
            dfs(nextPos, count + 1);
            passed[board[nextPos.first][nextPos.second] - 'A'] = false;
        }
    }
}

int main(int argc, const char * argv[])
{
    dir.push_back({0,1});
    dir.push_back({0,-1});
    dir.push_back({1,0});
    dir.push_back({-1,0});
    
    cin >> height >> width;
    
    board.assign(height, vector<char>(width));
    passed.assign(26, false);
    
    for (int i = 0; height > i; i++)
    {
        for (int j = 0; width > j; j++)
        {
            char ch;
            cin >> ch;
            board[i][j] = ch;
        }
    }
    
    //첫번째 위치(0,0)은 항상 방문한 상태이기 때문에 방문표시 & 깊이를 1칸으로 시작한다. 
    passed[board[0][0] - 'A'] = true;
    dfs(make_pair(0, 0), 1);
    
    cout << answer;
    
    return 0;
}