문제

문제 링크

해설

• 알파벳은 비트마스킹과 궁합이 정말 좋습니다.
• 알파벳은 26개라 2²⁶(67,108,864)로 int형 변수 1개의 0번부터 25번 bit을 조작해 표현할 수 있습니다.
• 이 문제는 중복 알파벳 칸을 지나갈 수 없기 때문에 지나간 알파벳을 기억하고 있어야 합니다.
  • DFS를 사용한다면: 평소처럼 전역변수를 사용하면 됩니다.
  • BFS를 사용한다면: 위에서 얘기한 비트마스킹을 사용해서 int형 변수 하나를 좌표와 함께 계속 끌고갑니다.
  • (참고로 이 문제는 BFS로 풀 수는 있지만, DFS로 푸는 것이 압도적으로 빠르고, 메모리도 훨씬 덜 먹습니다.)

코드

DFS 풀이

#include <iostream>
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;	// 좌표(y, x) + 지나온 알파벳 기록
    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;
}

소스코드 링크

결과