백준 1987번 [알파벳](C++) -yes6686- 티스토리

백준 문제 풀이: 1987 [알파벳]

---

문제 링크: https://www.acmicpc.net/problem/1987

문제 설명:

R×C 크기의 보드에서 말이 이동하며, 지나간 칸에 적힌 알파벳을 기억합니다. 말은 상하좌우로 이동할 수 있으며, 한 번 지나간 알파벳이 적힌 칸은 다시 지나갈 수 없습니다. 말이 최대로 이동할 수 있는 칸 수를 출력하는 프로그램을 작성하세요.

입력:

• 첫 번째 줄에 보드의 크기 R, C가 주어집니다. (1 ≤ R, C ≤ 20)
• 다음 R개의 줄에는 각 칸에 적힌 알파벳이 주어집니다. 알파벳은 대문자 영어 알파벳(A-Z)입니다.

출력:

• 말이 최대로 이동할 수 있는 칸 수를 출력합니다.

---

문제 해결 코드

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

int dx[4] = {1, -1, 0, 0}; // 상하좌우 이동
int dy[4] = {0, 0, 1, -1};
int r, c; // 보드의 크기
char board[21][21]; // 보드
bool visitedAlpha[26]; // 알파벳 방문 여부
int maxSteps = 0; // 최대로 이동한 칸 수

// DFS 탐색
void dfs(int x, int y, int steps) {
    maxSteps = max(maxSteps, steps); // 최대 칸 수 갱신

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 보드 범위를 벗어나거나 이미 방문한 알파벳인 경우 무시
        if (nx < 0 || ny < 0 || nx >= r || ny >= c || visitedAlpha[board[nx][ny] - 'A']) {
            continue;
        }

        // 현재 알파벳 방문 표시
        visitedAlpha[board[nx][ny] - 'A'] = true;

        // 다음 위치 탐색
        dfs(nx, ny, steps + 1);

        // 탐색 후 알파벳 방문 해제
        visitedAlpha[board[nx][ny] - 'A'] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> r >> c;

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }

    // 시작 위치의 알파벳 방문 표시
    visitedAlpha[board[0][0] - 'A'] = true;

    // DFS 탐색 시작
    dfs(0, 0, 1);

    cout << maxSteps << '\n';
    return 0;
}

예제

입력:
3 4
ABCD
EFGH
IJKL

출력:
12

입력:
2 2
AA
AB

출력:
3

---

코드 설명

• DFS 탐색: 상하좌우로 이동하며 방문하지 않은 알파벳만 탐색합니다.
• 알파벳 방문 체크: visitedAlpha 배열을 사용하여 방문한 알파벳을 기록합니다.
• 최대 이동 칸 수 갱신: maxSteps 변수를 통해 DFS 탐색 중 최대로 이동한 칸 수를 갱신합니다.

시간 복잡도

• 보드의 크기와 알파벳의 제한으로 인해 DFS의 최대 탐색 깊이는 26입니다.
• 각 칸에서 4방향을 탐색하므로 시간 복잡도는 O(4^min(RC, 26))입니다.

---

결과

코드는 입력된 보드에서 말이 최대로 이동할 수 있는 칸 수를 정확히 계산합니다. 보드 크기가 작으므로 모든 경우를 DFS로 탐색해도 효율적으로 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!