[백준] 1987: 알파벳 (C++)

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

문제

---

좌표의 크기가 주어지고, (1,1)부터 시작하는데 같은 알파벳을 만나면 안될때 까지 상하좌우로 움직일 시 최대한 많이 갈 수 있는 칸은 몇인지 찾는 문제이다.

아이디어

---

DFS와 백트래킹을 이용한다.

인접한 상하좌우 좌표를 확인하여 기록된 알파벳이 없으면 DFS를 호출한다.

 

여기서 백트래킹을 추가하여 DFS를 통해 visited(알파벳)을 기록하는데 갈수 있는 곳 까지 간 후 다시 visited를 해제하는 방식을 이용한다.

위 GIF는 문제의 예제로 백트래킹과 DFS가 어떻게 동작하는 지 그림판으로 나타내보았다.

 

H-A에서

H-A-D-G-J-F

H-A-J-G-D

H-A-J-F-D

의 DFS가 적용되고

 

H-F에서

H-F-J-A-D-G

H-F-J-G-D-A

H-F-J-G-A (GIF에는 실수로 못넣었다 더있을수도..)

H-F-D

이런식으로 총 7번의 경우 중 6칸을 움직이는 게 최대가 된다.

 

매번 칸을 이동할 때 마다 maxPathLength의 길이와 비교하여 최대값을 저장시켜준다.

 

Code

---

#include <algorithm>
#include <iostream>
#define MAX 20

using namespace std;

int R, C;                    // 행과 열의 크기
char board[MAX][MAX];        // 보드에 쓰여진 알파벳을 저장하는 배열
bool visited[26] = {false};  // 방문한 알파벳을 추적하는 배열

// 네 방향 이동을 위한 변화량: 상, 하, 좌, 우
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int maxPathLength = 0;  // 최대 경로 길이


void dfs(int row, int col, int pathLength) {
    // max
    maxPathLength = max(pathLength, maxPathLength);

    // 네 방향 탐색
    for (int dir = 0; dir < 4; ++dir) {
        int newRow = row + dx[dir];
        int newCol = col + dy[dir];

        // 보드 범위 내에 있고, 방문하지 않은 알파벳이면 탐색
        if (newRow >= 0 && newRow < R && newCol >= 0 && newCol < C) {
            int idx = board[newRow][newCol] - 'A';

            if (!visited[idx]) {
                visited[idx] = true;
                dfs(newRow, newCol, pathLength + 1);
                visited[idx] = false;  // 방문 상태 원상 복귀
            }
        }
    }
}

void init() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
}

int main() {
    init();
    cin >> R >> C;

    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> board[i][j];
        }
    }
    
    visited[board[0][0] - 'A'] = true;
    //  dfs(int row, int col, int pathLength)
    dfs(0, 0, 1);

    cout << maxPathLength << endl;
    return 0;
}