백준 A와 B 2 (12919번) C++

백준 A와 B 2 (12919번) C++ 풀이

문제 설명

문제

• 주어진 문자열 S를 문자열 T로 변환할 수 있는지 확인하는 문제입니다.
• 사용 가능한 연산:
• 1. 문자열 뒤에 'A'를 추가.
• 2. 문자열 뒤에 'B'를 추가하고 문자열을 뒤집기.
• 입력:
• 첫 줄: 문자열 S (길이 ≤ 49).
• 둘째 줄: 문자열 T (길이 ≤ 50, S의 길이 < T의 길이).
• S와 T는 'A'와 'B'로만 구성됨.
• 출력:
• S를 T로 만들 수 있으면 1, 아니면 0.

테스트 케이스

• 입력:

A
BABA

• 출력: 1
• 설명: S = "A"를 연산을 통해 T = "BABA"로 만들 수 있음.

문제 작동 원리

• 역방향 접근: S에서 T로 가는 대신, T에서 S로 줄이는 역연산을 사용.
• 역연산 1: T의 마지막 문자가 'A'면 'A' 제거.
• 역연산 2: T의 첫 문자가 'B'면 첫 'B'를 제거하고 나머지를 뒤집기.
• 테스트 케이스 (S = "A", T = "BABA"):
• T = "BABA" (길이 4)에서 S = "A" (길이 1)로 줄이는 과정:
• 초기 상태: str = "BABA", index = 4.
• 분기 1 (마지막 'A' 제거):
• str[3] = 'A' → new_str = "BAB".
• DFS(3, "BAB"):
• 첫 'B' → reverse_str(str) → "BAB" → str[2] = '\0' → new_str = "BA".
• DFS(2, "BA"):
• 첫 'B' → reverse_str(str) → "AB" → str[1] = '\0' → new_str = "A".
• DFS(1, "A"): index == strLen1, strcmp("A", "A") == 0 → true.
• 결과: 성공 → result = true.
• 분기 2 (첫 'B' 제거 후 뒤집기):
• str[0] = 'B' → reverse_str(str) → "ABAB" → str[3] = '\0' → new_str = "ABA".
• DFS(3, "ABA"): 추가 탐색 필요 시 진행, 하지만 분기 1에서 이미 성공.
• 결과: result = true → 출력: 1.
• 원리: 재귀(DFS)로 T에서 S로 줄이는 모든 경로를 탐색. 한 경로라도 S에 도달하면 1 출력.

아이디어

• 재귀(DFS):
• T에서 S로 줄이는 역연산을 재귀 함수 DFS로 구현.
• 각 상태에서 두 역연산(마지막 'A' 제거, 첫 'B' 제거 후 뒤집기)을 시도.
• 분기 처리:
• result |= DFS(...)로 두 분기(마지막 'A' 제거, 첫 'B' 제거 후 뒤집기) 결과를 누적.
• 길이가 S와 같아지면 strcmp으로 비교.
• 상태 관리:
• 각 분기에서 new_str에 문자열 복사해 상태 충돌 방지 시도.
• 주의: 분기 2에서 str을 먼저 뒤집고 수정하므로, 일부 케이스에서 잘못된 경로 탐색 가능.
• STL 활용:
• cstring: strlen, strcmp으로 길이 계산과 문자열 비교.
• iostream: cin, cout으로 입력/출력.
• algorithm: swap으로 문자열 뒤집기.

전체 코드

#include <iostream>
#include <cstring>
#lt;algorithm>

using namespace std;

void reverse_str(char* str)
{
    int left=0;
    int right=(int)strlen(str)-1;
    
    while(left<right)
    {
        swap(str[left],str[right]);
        left++;
        right--;
    }
}

int strLen1;
int strLen2;
char str1[100],str2[100];
bool DFS(int index, char* str)
{
    if(index==strLen1 && strcmp(str1,str)==0)
        return true;
    bool result=false;
    if(str[index-1]=='A')
    {
        char new_str[51];
        for(int i=0;str[i]!='\0';i++)
            new_str[i]=str[i];
        new_str[index-1]='\0';
        result |= DFS(index - 1, new_str);
    }
    
    if(str[0]=='B')
    {
        reverse_str(str);
        str[index-1]='\0';
        char new_str[51];
        for(int i=0;str[i]!='\0';i++)
            new_str[i]=str[i];
        new_str[index-1]='\0';
        result |= DFS(index - 1, new_str);
    }
    
    return result;
}

int main(void)
{
    cin>>str1>>str2;
    strLen1=(int)strlen(str1);
    strLen2=(int)strlen(str2);
    
    if(DFS(strLen2,str2))
        cout<<1<<endl;
    else
        cout<<0<<endl;
    
    return 0;
}

---

결론

• 역방향 접근 효과: S에서 T로 가는 대신 T에서 S로 줄이는 방식으로 문제 단순화.
• 재귀와 분기: DFS로 모든 경로 탐색, result |=로 두 분기 처리.
• 주의점: 분기 2에서 str을 먼저 뒤집고 수정하므로 상태 충돌 가능. 일부 케이스에서 우연히 정답.
• 개선 제안: 분기 2에서 str 수정 전에 new_str에 복사하고, 첫 'B' 제거 후 뒤집기로 수정하면 더 안전.