문제

문제 링크

해설

아주 전형적으로 DFS 재귀로도 풀 수 있고, 최적값을 찾는 문제이기도 하므로 BFS로도 풀 수 있는 문제입니다. (미리 말씀드리지만, DFS가 훨씬 빠르게 풀 수 있는 문제입니다.)

DFS (재귀)

• 같은 알파벳이 적힌 칸을 두 번 지날 수 없기 때문에 26개의 알파벳을 각각 지났는지 지나지 않았는지 체크하는 bool 타입의 배열을 만듭니다.
• 전형적으로 'set' → 'DFS 수행' → 'reset'으로 DFS를 진행합니다.
  • 즉, 방문표시를 한 뒤 더 추가적인 깊은 DFS를 진행한 뒤 반환됐을 때 방문표시를 해제합니다.
• 최대로 지날 수 있는 칸의 개수가 궁금하므로, 재귀의 깊이가 가장 많이 들어간 때를 체크하면 됩니다.

BFS

• 이러한 종류를 보통 DFS로 해결하는 이유는
  1. visited 배열을 끌고가지 않아도 되기 때문입니다. (재귀 방식은 어떤 것을 set 했을 때를 기준으로 더 이상 진행 불가능 할 때까지 계속 깊게 파고 들어가기 때문에 visited 배열을 계속 달고 다닐 필요가 없습니다.)
  2. 훨씬 간단하게 프로그램을 작성할 수 있기 때문입니다.
• 그럼에도 불구하고 '최적값을 구하는 것' 때문에 당장에 BFS 풀이방식 밖에 떠오르지 않을 수 있습니다.
• 다행히 알파벳은 26개이므로 32-bit로 표현할 수 있습니다.
  • 즉, int형 정수 1개만으로 각 비트를 set/reset 하는 방식으로 현재까지 어떤 알파벳을 지나왔는지 visited 배열처럼 사용할 수 있습니다.
  • 따라서, queue에 현재 좌표 + 현재까지 지나온 알파벳 정보를 담은 32-bit int형 정수를 넣어 BFS를 수행합니다.
• 계속 visited 배열을 끌고 가는 것보다는 이 방법이 훨씬 효율적으로 풀 수 있습니다.
  • (어쩌면 이 방법을 사용했기 때문에 그나마 BFS로 풀 수 있던 것일 수도 있습니다.)
  • (왜냐하면 이 방법으로 풀어도 메모리를 약 215MB, 시간은 1604ms로 메모리제한 + 시간제한에 거의 걸릴 뻔 했기 때문입니다.)

코드

DFS

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int R, C, answer;
char board[20][20];
bool alpha[26];

void solve(int cy, int cx, int cnt)
{
    answer = max(answer, cnt);
    for (auto i : d) {
        int ny = cy + i[0], nx = cx + i[1];
        if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
        int next_alpha = board[ny][nx] - 'A';
        if (alpha[next_alpha]) continue;
        
        alpha[next_alpha] = true;
        solve(ny, nx, cnt + 1);
        alpha[next_alpha] = false;
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> R >> C;
    for (int y = 0; y < R; y++)
        for (int x = 0; x < C; x++)
            cin >> board[y][x];

    alpha[board[0][0] - 'A'] = true;
    solve(0, 0, 1);
    cout << answer << '\n';
    return 0;
}

소스코드 링크

BFS

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int R, C;
char board[20][20];

int get_length(int num) {
    int ret = 0;
    for (int i = 0; i < 32; i++)
        if (num & (1 << i)) ret++;
    return ret;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> R >> C;
    for (int y = 0; y < R; y++)
        for (int x = 0; x < C; x++)
            cin >> board[y][x];

    queue<tuple<int, int, int>> q;
    q.emplace(0, 0, (1 << (board[0][0] - 'A'))); 

    int answer = 1;
    while (!q.empty()) {
        int cy, cx, history; tie(cy, cx, history) = q.front();
        q.pop();
        answer = max(answer, get_length(history));
        for (auto i : d) {
            int ny = cy + i[0], nx = cx + i[1];
            if (ny < 0 || nx < 0 || ny >= R || nx >= C || 
                (history & (1 << (board[ny][nx] - 'A')))) continue;
            q.emplace(ny, nx, history | (1 << (board[ny][nx] - 'A')));
        }
    }
    cout << answer << '\n';
    return 0;
}

소스코드 링크

결과