[BOJ 1987] 알파벳

1987번: 알파벳

 

이전에 파이썬으로 푼 적이 있는 문제인데 데이터 추가로 재채점이 된 이후 시간초과로 틀린 문제 처리되어 이번에 C++로 다시 풀어보았다!

 

1. 문제 설명

예제 입력 1의 경우 C-A-D, 예제 입력 2의 경우 H-A-D-G-J-F로 갈 경우 최대여서 각각 3, 6을 출력한다.

 

2. 구현 아이디어 1 - 맞았습니다 !!

최대로 움직일 수 있는 칸, 즉 가장 '깊게' 들어갈 수 있는 칸 수를 세어야 하므로 DFS를 사용해야 한다.

 

이미 지나온 알파벳인지 확인하기 위해서는 26칸짜리 1차원 배열을 사용했다.

배열에서 0번째 칸은 A, 1번째 칸은 B ... 를 의미하며, visited[board[i][j]-'A']와 같이 접근했다.

 

처음에는 stack을 활용하여 DFS를 구현하고자 하였으나, 현재 경로가 가장 깊게 들어갈 수 있는 경우가 아닐 때 지나온 길에 있던 알파벳의 방문 여부를 무효 처리해주어야 한다. 즉, DFS+백트래킹 문제이다.

그러므로 stack이 아닌 재귀 방식으로 DFS를 구현하였다.

 

#include <bits/stdc++.h>

using namespace std;

int r, c;
char board[22][22];

bool visited[26];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int ret;

// 인접한 네 칸 중 이동할 칸이 있는지 확인
bool canGo(int cx, int cy) {
    int nx, ny;
    bool cg = false;
    for (int i = 0; i < 4; ++i) {
        nx = cx + dx[i];
        ny = cy + dy[i];

        // index out of range
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        // 이미 지나온 알파벳
        if (visited[board[nx][ny]-'A']) continue;
        cg = true;
    }

    return cg;
}

void dfs(int cx, int cy, int cnt) {
    // 종료 조건: 더 이상 진전할 칸이 없을 때
    if (!canGo(cx, cy)) {
        if (cnt > ret) ret = cnt;
        visited[board[cx][cy]-'A'] = false;
        return;
    }

    int nx, ny;
    for (int i = 0; i < 4; ++i) {
        nx = cx + dx[i];
        ny = cy + dy[i];

        // index out of range
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        // 이미 지나온 알파벳
        if (visited[board[nx][ny]-'A']) continue;

        visited[board[nx][ny]-'A'] = true;
        dfs(nx, ny, cnt+1);
        visited[board[nx][ny]-'A'] = false;
    }
}

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

    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(0, 0, 1);

    cout << ret;

    return 0;
}

 

나 같은 경우 main 함수 위에 전역 변수로 사용할 변수들을 미리 선언해두고 사용하는 것을 좋아한다. (default 값으로 자동 초기화되고, 메모리 절약된다는 글을 봐서)

 

하지만 nx, ny를 전역 변수 처리하니 canGo 함수에서 사용했던 nx, ny가 dfs 함수에도 적용되어 cx, cy, nx, ny가 원하던대로 움직이지 않았었다.

 

함수가 2개 이상일 때 변수가 겹쳐서 값이 이상하게 들어가지 않도록 주의하자.