[C++ 백준 풀이] 1987번 : 알파벳 / 9252번 : LCS 2 (DFS, 공통 문자열)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 1987번 : 알파벳, 9252번 : LCS 2 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 난이도 Gold에 해당하며, 각각 DFS와 공통 문자열 알고리즘에 대한 배경지식이 필요한 문제입니다.

 

 

1987번 : 알파벳

 

지도에 각 좌표에 대해 알파벳으로 주어진 입력이 있을 때, 1행 1열에서 출발하여 중복된 알파벳을 거치지 않고 최대 몇 개의 칸을 거칠 수 있는지 구하는 문제입니다.

다른 문제들과 형태가 비슷하나, 알파벳을 기록하면서 탐색을 수행해야 한다는 것이 특징적인 문제입니다.

간단한 DFS로 해결해보도록 하겠습니다.

 

 

↓ 위의 이미지와 동일한 소스 코드는 아래 접은 글에 정리되어 있으니 참고해주세요.

#include <iostream>
using namespace std;

char Map[25][25];
bool check[26] = {0, };
int unit[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int R, C, Max = 0;

void DFS(int y, int x, int cnt) {
    for(int i=0; i<4; i++) {
        int next_y = y + unit[i][0], next_x = x + unit[i][1];
        if(next_y >= 0 && next_y < R && next_x >= 0 && next_x < C && !check[Map[next_y][next_x]-'A']) {
            check[Map[next_y][next_x]-'A'] = 1;
            DFS(next_y, next_x, cnt+1);
            check[Map[next_y][next_x]-'A'] = 0;
        }
    }
    if(cnt > Max) Max = cnt;
}

int main() {
    cin >> R >> C;
    for(int i=0; i<R; i++) cin >> Map[i];
    check[Map[0][0]-'A'] = 1;
    DFS(0, 0, 1);
    cout << Max;
}

 

먼저 Map이라는 배열을 선언하여 알파벳들을 입력받습니다.

이 때 %1c와 같은 입력으로 처리하지 않고 한 줄씩 입력을 받았는데, 개행 문자 역시 char 형태이기 때문에 이를 처리하기 애매해서 그랬습니다.

입력 받은 이후에는 DFS 함수를 실행했는데, DFS 함수는 한 칸을 이동할 때마다 check라는 배열에서 26칸의 알파벳 중 어떤 알파벳을 거쳤는지를 기록하며 확인합니다.

기존 DFS의 visit 배열이 check 배열의 알파벳 검사로 바뀐 형태일 뿐이기 때문에, 큰 틀의 관점에서는 달라질 것이 없습니다.

 

 

채점을 수행해보면 508ms라는 비교적 오랜 시간이 걸리면서 정답 처리가 됨을 확인할 수 있습니다.

이는 탐색 알고리즘 자체가 비효율적이라서 그랬을 수도 있고, 입출력 과정에서 딜레이가 많이 생겨서 그랬을 수도 있다고 생각합니다.

 

 

9252번 : LCS 2

 

최장 공통 부분 수열, 즉 LCS를 찾는 문제입니다.

저는 이전에 LCS 1 문제도 풀이한 적이 있으나, 따로 다룬 적이 없었기에 이 문제를 풀이해보도록 하겠습니다.

최장 공통 부분 수열을 찾는 알고리즘은 두 문자열을 각각 행, 열에 적어놓고 N×M 표를 채워나가는 방식으로 계산하는 알고리즘이 대표적입니다.

처음에는 0에서 시작해서, 문자열 A의 i번째 문자와 문자열 B의 j번째 문자가 동일하면 i-1행 j-1열 값 + 1을 적어주고, 그렇지 않다면 i-1행 j열의 값과 i행의 j-1열의 값 중에서 큰 값을 적어주는 것입니다.

이러면 문자열이 겹칠 때마다 +1 값이 되어서 표에서 가장 큰 값이 결국 LCS의 길이가 됩니다.

 

 

↓ 위의 이미지와 동일한 소스 코드는 아래 접은 글에 정리되어 있습니다.

#include <iostream>
#include <string>
using namespace std;

int dp[1005][1005] = {0, };
int Max(int a, int b) { return a>b?a:b; }
string A, B;

void print_LCS(int i, int j) {
    if(!dp[i][j]) return;
    if(A[i-1] == B[j-1]) {
        print_LCS(i-1, j-1);
        cout << A[i-1];
    }
    else {
        if(dp[i-1][j] > dp[i][j-1]) print_LCS(i-1, j);
        else print_LCS(i, j-1);
    }
}

int main() {
    cin >> A >> B;
    for(int i=1; i<=A.length(); i++)
        for(int j=1; j<=B.length(); j++) {
            if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = Max(dp[i-1][j], dp[i][j-1]);
        }
    cout << dp[A.length()][B.length()] << "\n";
    print_LCS(A.length(), B.length());
}

 

단순히 LCS의 길이를 찾는 것이 LCS 1 문제였다면, 이 문제는 LCS 문자열을 직접 찾아야 하기 때문에 이를 어떻게 출력할지 모를 수도 있습니다.

하지만 이는 위에서 언급한 표를 직접 그려보면 알 수 있는데, 바로 표를 채워나가는 과정을 역으로 수행해나가면서 역순으로 출력해주면 됩니다.

두 문자열의 i번째 문자와 j번째 문자가 일치하면 i-1행 j-1열 값 + 1이라고 하였으므로, 역으로 i번째 문자와 j번째 문자가 일치하다면 재귀적으로 i-1번째 문자와 j-1번째 문자에 대해서도 같은 수행을 반복해주면 됩니다.

이 때 역순으로 출력해야 하므로 호출을 먼저 해주고 출력을 나중에 수행하도록 해줍니다.

 

 

작성한 풀이 코드를 제출해보면 4ms라는 짧은 시간에 채점이 완료됨을 확인할 수 있습니다.

보아하니 LCS 시리즈 문제들과 관련해서 문제들이 더 있는 것으로 보이는데 시간이 나면 시리즈 문제들도 풀이해보도록 하겠습니다.