C - [백준 1987] 알파벳 (feat. 백트래킹, DFS & 최장거리 탐색)

참고 포스트

 

2024.12.25 - [Computer Science/알고리즘 문제] - C - [백준 2178] 미로탐색 (feat. BFS & 최단거리 탐색)

C - [백준 2178] 미로탐색 (feat. BFS & 최단거리 탐색)

2024.12.30 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)

[자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)

 

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

 

BOJ 1987 알파벳

문제 요약

1. R×C 크기의 보드 위에 알파벳이 적혀 있습니다.
2. (0, 0) 위치에서 시작하여 상하좌우로 이동할 수 있습니다.
3. 이동 중 같은 알파벳이 적힌 칸을 두 번 지나갈 수 없습니다.
4. 더 이상 이동할 수 없을 때까지 이동한 칸의 최대 개수를 구하는 문제입니다.

입력 형식

1. 첫 줄에 보드의 크기 R(행)과 C(열)이 주어집니다. (1 ≤ R, C ≤ 20)
2. 다음 R개의 줄에 각 줄마다 C개의 대문자 알파벳이 적힌 문자열이 주어집니다.

 

출력 형식

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

 

문제 이해 예제

CAAB
ADCB

• 시작 위치는 (0, 0)이며, C에서 시작합니다.
• 가능한 경로:
  1. (0, 0) → (1, 0) → (1, 1) (C → A → D) → 최대 3칸
  2. (0, 0) → (0, 1) → (1, 1) → 더 이상 이동 불가 (C → A → D)

결과적으로 최대 이동 칸 수는 3입니다.

 

---

Checkpoint

1.

최대 이동 칸 수, 즉 최장거리를 구해야하는 문제이므로 깊이 우선 탐색(DFS) 알고리즘이 필요합니다.

(BFS로 구현해서 테스트 해보려고 했는데 오류 빡빡 떠서 빠른 포기)

 

BFS를 이용한 미로탐색(https://rnasterofmysea.tistory.com/51) 문제의 핵심 알고리즘이었던 상하좌우 처리에 DFS 및 백트래킹 알고리즘을 잘 섞으면 금방 해결할 수 있는 문제였습니다.

 

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

// 생략

for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        // 배열 범위 체크 및 새로운 알파벳인지 확인
        if (0 <= nx && nx < C && 0 <= ny && ny < R && alphabet_check[board[ny][nx] - 'A'] == 0) {
            dfs(nx, ny, count + 1);
        }
    }

 

2.

이번 문제는 기존에 사용하던 재귀 함수 구조와는 다른 점이 있었습니다. 일반적으로 재귀 함수에서는 특정 조건이 만족되면 함수를 종료하는 기저 조건을 명시적으로 설정합니다. 하지만 이번 문제에서는 기저 조건을 따로 명시하지 않고, 이동할 수 있는 경로가 더 이상 없을 경우 재귀 호출이 자연스럽게 종료되는 방식으로 구현되었습니다.

 

void dfs(int x, int y, int count) {
    // 현재 알파벳 방문 체크
    alphabet_check[board[y][x] - 'A'] = 1;

    // 최대값 갱신
    if (MAX < count) {
        MAX = count;
    }

    // 4방향 탐색
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        // 배열 범위 체크 및 새로운 알파벳인지 확인
        if (0 <= nx && nx < C && 0 <= ny && ny < R && alphabet_check[board[ny][nx] - 'A'] == 0) {
            dfs(nx, ny, count + 1);
        }
    }

    // 탐색 종료 후 현재 알파벳 방문 해제 (백트래킹)
    alphabet_check[board[y][x] - 'A'] = 0;
}

 

3.

또한, 백트래킹을 구현하는 과정에서, 탐색을 마친 뒤로 돌아가는 상태 복원 작업이 재귀 호출 바로 직후가 아니라 별도로 분리되어 있다는 점이 독특했습니다.

    // 탐색 종료 후 현재 알파벳 방문 해제 (백트래킹)
    alphabet_check[board[y][x] - 'A'] = 0;

 

일반적으로는 재귀 호출과 상태 복원이 밀접하게 연결되어 있는 경우가 많지만, 이번 문제에서는 탐색을 모두 완료한 이후에 방문 상태를 해제하는 방식으로 백트래킹이 구현되었습니다.

하단은 N-Queen 문제(https://rnasterofmysea.tistory.com/70)의 재귀 구조입니다,  재귀 호출과 상태복원이 연속적으로 작동됩니다.  Checkpoint 2에 제시한 현 문제의 DFS 구조에서는 재귀 함수 내부에서 방문 헤제가 이뤄집니다.

 

void solve_nqueen(int row) {
    // 1. 기저 조건
    if (row == N) {
        count_solutions++;
        return;
    }

    // 2. 현재 상태 처리
    for (int col = 0; col < N; col++) {
        if (is_safe(row, col)) {
            place_queen(row, col);  // 퀸 배치

            // 3. 재귀 호출
            solve_nqueen(row + 1);

            // 4. 상태 복원 (백트래킹)
            remove_queen(row, col);  // 퀸 제거
        }
    }
}

 

 

이를 통해 백트래킹을 구현할 때는 단순히 기저 조건을 설정하는 것에 그치지 않고, 언제 상태를 복원할 것인지 명확히 고려해야 한다는 점을 고려해서 설계해야한다는 것을 알게되었습니다.

 

4. 개선점

알파벳 방문 여부를 비트마스크로 처리하면 메모리를 효율적으로 사용할 수 있습니다(chatGPT왈).

---

 

구현 코드

/*
BOJ_1987_알파벳
https://www.acmicpc.net/problem/1987

*/

#include <stdio.h>

int alphabet_check[26]; // 알파벳 방문 여부 체크
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
char board[20][20];
int C, R; // 가로, 세로
int MAX = 0;

void dfs(int x, int y, int count) {
    // 현재 알파벳 방문 체크
    alphabet_check[board[y][x] - 'A'] = 1;

    // 최대값 갱신
    if (MAX < count) {
        MAX = count;
    }

    // 4방향 탐색
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        // 배열 범위 체크 및 새로운 알파벳인지 확인
        if (0 <= nx && nx < C && 0 <= ny && ny < R && alphabet_check[board[ny][nx] - 'A'] == 0) {
            dfs(nx, ny, count + 1);
        }
    }

    // 탐색 종료 후 현재 알파벳 방문 해제
    alphabet_check[board[y][x] - 'A'] = 0;
}

int main() {
    // 입력
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) {
        scanf("%s", board[i]);
    }

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

    // 결과 출력
    printf("%d", MAX);
    return 0;
}

 

1. 전역 변수 정의

int alphabet_check[26]; // 알파벳 방문 여부 체크
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; // 이동 방향
char board[20][20]; // 입력 보드 (최대 크기: 20x20)
int C, R; // 보드의 가로(C), 세로(R)
int MAX = 0; // 최대 이동 칸 수

• alphabet_check: 현재까지 방문한 알파벳을 체크하는 배열입니다. 알파벳 A부터 Z는 26개로 고정되어 있기 때문에 26칸 배열을 사용합니다.
• dir: 말이 상하좌우로 이동할 때의 좌표 변화 값을 저장합니다.
• board: 입력 보드를 저장하는 배열입니다.
• MAX: 탐색 중 최대 이동 칸 수를 저장하는 변수입니다.

---

2. DFS 함수

void dfs(int x, int y, int count) {
    // 현재 알파벳 방문 체크
    alphabet_check[board[y][x] - 'A'] = 1;

    // 최대값 갱신
    if (MAX < count) {
        MAX = count;
    }

    // 4방향 탐색
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        // 배열 범위 체크 및 새로운 알파벳인지 확인
        if (0 <= nx && nx < C && 0 <= ny && ny < R && alphabet_check[board[ny][nx] - 'A'] == 0) {
            dfs(nx, ny, count + 1);
        }
    }

    // 탐색 종료 후 현재 알파벳 방문 해제
    alphabet_check[board[y][x] - 'A'] = 0;
}

세부 동작

 

1. 현재 위치 알파벳 방문 처리:

• board[y][x]에서 알파벳을 숫자 인덱스(A를 0으로)로 변환한 뒤 방문 상태를 기록합니다.

alphabet_check[board[y][x] - 'A'] = 1;

 

2. 최대 칸 수 갱신:

• 현재까지 탐색한 경로의 칸 수를 최대값과 비교하여 갱신합니다.

if (MAX < count) { MAX = count; }

 

4방향 탐색:

• 상하좌우로 이동 가능한 좌표를 계산하고, 이동할 수 있는 경우(범위 내 && 새로운 알파벳)에만 재귀 호출합니다.

for (int i = 0; i < 4; i++) {
	int nx = x + dir[i][0];
    int ny = y + dir[i][1];
    if (0 <= nx && nx < C && 0 <= ny && ny < R && alphabet_check[board[ny][nx] - 'A'] == 0) {
    	dfs(nx, ny, count + 1);
	}
}

1. 백트래킹:
   • 재귀 탐색이 끝난 후, 현재 알파벳의 방문 상태를 해제하여 다른 경로에서도 다시 탐색할 수 있도록 합니다.

alphabet_check[board[y][x] - 'A'] = 0;

---

3. 메인 함수

int main() {
    // 입력
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) {
        scanf("%s", board[i]);
    }

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

    // 결과 출력
    printf("%d", MAX);
    return 0;
}

동작 과정

1. 보드 입력:
   • 보드의 크기(R, C)와 각 칸의 알파벳을 입력받아 board 배열에 저장합니다.
2. DFS 호출:
   • 시작 좌표 (0, 0)에서 탐색을 시작하며 초기 경로 길이는 1로 설정합니다.
3. 결과 출력:
   • DFS 탐색 후, MAX 값(최대 이동 칸 수)을 출력합니다.

---

예제 입력/출력

입력 예시

2 4
CAAB
ADCB

출력 예시

3

동작 설명

1. (0, 0)에서 시작하여 가능한 모든 경로를 탐색합니다.
2. 예를 들어, 다음과 같은 경로가 탐색됩니다:
   • C → A → D (최대 3칸)
   • 다른 경로는 중간에 중복 알파벳이 있어 탐색이 종료됩니다.
3. 최종적으로 최대 이동 칸 수는 3입니다.

---

핵심 포인트

• DFS와 백트래킹:
  • 모든 가능한 경로를 탐색하며 최적의 결과를 찾습니다.
  • 재귀 호출 후 방문 상태를 초기화하여 다른 경로 탐색을 가능하게 합니다.
• 시간 복잡도:
  • 알파벳 방문 여부(26개)와 보드 크기 탐색(R×C)을 고려하면, 최악의 경우 탐색은 O(26 × R × C)입니다.
• 알파벳 문제 특성:
  • 알파벳을 효율적으로 관리하기 위해 alphabet_check 배열을 사용했습니다.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.