[백준] 12904 A와 B (BruteForce) - Python / 자세한 설명 / 골드5

백준 로고

 

 

Contents

---

 

1. 문제 정의 및 예제 해석

(문제 링크: https://www.acmicpc.net/problem/12904 )

12904번: A와 B

B : 문자열 S
ABBA :  문자열 T

아래와 같은 2가지 규칙을 지키며, 문자열 S를 문자열 T로 바꿀 수 있으면 1을, 바꿀 수 없으면 0을 출력하는 문제입니다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

첫 번째 예제에 대해 B가 ABBA가 되는 과정을 살펴보겠습니다.

B -> BA(뒤에 A 추가) A 추가) -> ABB(뒤집고 B추가) -> ABBA(뒤에 A 추가)

 

2. 전체 코드

import sys
sys.setrecursionlimit(10**6) # 재귀 호출 리밋 올리기
S=list(input())
T=list(input())
def dfs(t):
    if t==S:
        print(1)
        sys.exit()
    if len(t)==0:
        return
    if t[-1]=='A': # 마지막이 A이면
        dfs(t[:-1]) # 제거하고, 재귀
    if t[-1]=='B': # 마지막이 B이면
        dfs(t[:-1][::-1]) # 제거하고, 뒤집어서 재귀
dfs(T)
print(0)

 

3. 일반 풀이 해설

1) 입력 및 재귀 한계 설정

import sys
sys.setrecursionlimit(10**6) # 재귀 호출 리밋 올리기
S=list(input())
T=list(input())

* 코드 설명

sys라이브러리는 재귀 호출의 한도를 상향시키는 것과, 중간에 S가 T로 바뀌는 경우 1을 출력하고 코드를 종료할 때(sys.exit()) 사용됩니다. 재귀 호출의 한도를 늘리는 코드는 sys.setrecursionlimit(10**6)입니다. 문자열 S와 T를 리스트로 입력받습니다. 예제 1번에 대해 S와 T를 입력받아 출력하면 아래와 같습니다.

*출력

예제1 S와 T 출력

 

2) dfs 함수 정의

def dfs(t):
    if t==S:
        print(1)
        sys.exit()
    if len(t)==0:
        return
    if t[-1]=='A': # 마지막이 A이면
        dfs(t[:-1]) # 제거하고, 재귀
    if t[-1]=='B': # 마지막이 B이면
        dfs(t[:-1][::-1]) # 제거하고, 뒤집어서 재귀

* 코드 설명

이 문제에서 핵심은 S를 T로 바꾸는 것이 아니라, 규칙을 반대로 적용해 T를 S로 바꾸는 것입니다. 규칙에 따라 S를 T로 바꾸려면 2^n승으로 경우의 수가 발산됩니다. 하지만, T를 S로 바꾼다면, T의 상태에 따라 마지막이 A로 끝나는 경우만 A를 지우고, B로 끝나는 경우만 B를 지우고 뒤집습니다. 즉, 한 번 연산에 T의 마지막 단어가 없어지며, T의 길이가 줄어들게 됩니다. 

 

이제 함수 dfs를 살펴보겠습니다. 문자열 T에 대해 리스트 형태가 t로 입력됩니다. t==S는 T가 S로 변환 가능한 경우로 1을 출력하고 코드를 종료합니다. 다음으로 if문 3개는 아래와 같은 동작을 합니다.

1. if len(t)==0: return 0 : t가 재귀적으로 줄어들다가, t의 길이가 0인 경우는 t가 S가 되지 못하고 길이가 0이 되어 버린 경우로 return으로 해당 함수를 종료시킵니다.
2. if t[-1]=='A': dfs(t[:-1]) : t의 마지막이 A로 끝나면, A를 제거하여 dfs를 재귀 호출합니다.
3. if t[-1]=='B': dfs(t[:-1][::-1]) : t의 마지막이 B로 끝나면, B를 제거하고, 뒤집어서 dfs를 재귀 호출합니다.

 

3) 함수 호출

dfs(T)
print(0)

* 코드 설명

리스트 형태의 T를 dfs에 호출하면, 재귀적으로 T의 길이가 줄어들며, S로 변환 가능한지 검사합니다. 재귀 호출이 모두 끝났는데도 1이 출력되고 코드가 종료되지 않았다는 것은 T가 S로 바뀔 수 없는 경우입니다. 그럴 땐 0을 출력하고 코드를 종료합니다.

 

5. 느낀 점

S를 T로 바꾸는 방식으로 접근하면 경우의 수가 너무 많고, 풀기 어렵습니다. 규칙을 거꾸로 적용해, T를 S로 바꾸는 방향으로 접근한다면 문제가 생각보다 쉽게 풀립니다.

 

읽어주셔서 정말 감사합니다.

다음에 더욱 재미있고 유익한 글로 찾아오겠습니다.