[백준] 1987 – 알파벳

문제

#1987: 알파벳(acmicpc.net)

설명

0, 0은 무조건 밟을 수만 있기 때문에 0을 true로 변경하고 DFS(0, 0, 1)로 함수를 시작합니다.

여기서 글자와 글자를 빼는 과정이 있는데 A가 지도상에 있었다면 65-65이므로 0번째 방문, B가 있으면 66-65이므로 1번째 방문알파벳은 이렇게 되어있다.

저장되었습니다.

이 문제의 핵심은 역추적(backtracking)이라는 DFS 함수의 실행 하에서 다시 방문한 배열을 잘못 만드는 부분이다.

나는 대부분의 그래프 문제가 유사한 코드 구조를 가지고 있어서 많은 문제를 접할 수 있다는 점이 좋습니다.

#include <iostream>
using namespace std;

int R, C, answer;
char map(20)(20);
bool visited(26);

void DFS(int x, int y, int count) {
    answer = max(answer, count);
    
    int dx() = { 0, 0, 1, -1 };
    int dy() = { 1, -1, 0, 0 };
    for (int i = 0; i < 4; i++) {
        int nx = x + dx(i);
        int ny = y + dy(i);

        if (nx < R && ny < C && nx >= 0 && ny >= 0) {
            if (visited(map(nx)(ny) - 'A') == false) {
                visited(map(nx)(ny) - 'A') = true;
                DFS(nx, ny, count + 1);
                visited(map(nx)(ny) - 'A') = false;
            }
        }
    }
}

int main() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map(i)(j);
        }
    }
    
    visited(map(0)(0) - 'A') = true;
    DFS(0, 0, 1);
 
    cout << answer;

    return 0;
}