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

백준 로고

 

 

Contents

 

---

 

1. 문제 정의 및 예제 해석

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

12919번: A와 B 2

예제 입력 및 출력

B : 문자열 S
BABA :  문자열 T

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

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

첫 번째 예제에 대해 다음과 같은 과정을 거치면 문자열 S가 T로 변환되는 것을 알 수 있습니다.

B -> BA(A 추가) -> BAB(B 추가하고 뒤집기) -> BABA(A 추가)

 

2. 전체 코드

import sys
S=list(input())
T=list(input())
def dfs(t): # 문자열 T 리스트를 입력받아
    if t==S:
        print(1)
        sys.exit()
    if len(t)==0:
        return 0
    if t[-1]=='A': # 마지막이 A이면 
        dfs(t[:-1]) # 제거해서 재귀
    if t[0]=='B': # 처음이 B이면
        dfs(t[1:][::-1]) # B제거하고, 뒤집어서 재귀
dfs(T)
print(0)

3. 일반 풀이 해설

1) 문자열 입력

import sys
S=list(input())
T=list(input())

* 코드 설명

sys 라이브러리는 중간에 문자열 S가 T로 바뀔 수 있다면 1을 출력하고 코드를 종료하기 위해 사용됩니다. 문자열 S와 T를 각각 리스트로 입력받습니다. 첫 번째 예제에 대해 S와 T를 출력하면 아래와 같습니다.

*출력

S와 T 출력

2) dfs 함수 정의

def dfs(t): # 문자열 T를 입력받아
    if t==S:
        print(1)
        sys.exit()
    if len(t)==0:
        return 0
    if t[-1]=='A': # 마지막이 A이면 
        dfs(t[:-1]) # 제거해서 재귀
    if t[0]=='B': # 처음이 B이면
        dfs(t[1:][::-1]) # B제거하고, 뒤집어서 재귀

* 코드 설명

핵심은 S를 T로 바꾸는 게 아니라, T를 S로 바꾸는 것입니다. S에서 T로 가기 위해서 뒤에 A 추가, 뒤에 B 추가하고 뒤집기라는 2가지 방법을 발산적으로 사용하게 되어 경우의 수가 너무 많습니다. 하지만 T에서 S로 간다면 T의 마지막에 A가 있으면 제거하고, T의 맨 앞이 B라면 맨 앞의 B를 제외하고, 문자열을 뒤집고 하는 방식으로 갑니다. 즉, 문자열 T의 상태에 따라 2가지 방식이 적용되므로 수렴적으로 사용된다는 것을 알 수 있습니다. 예를 들어, 문자열 T가 B로만 이루어져 있다면, A를 제거하는 연산은 하나도 사용되지 않게 됩니다. 

 

이제 함수 dfs에 대해 설명해보겠습니다. dfs함수에는 문자열T의 리스트가 t라는 변수로 입력받습니다. t가 S와 같으면 S를 T로 변환할 수 있다는 것이고 1을 출력하고 코드를 아예 종료(sys.exit())해버립니다. if len(t)==0: 부분은 t 리스트에서 문자열을 재귀적으로 제거하다가 모두 제거된 경우로 return 0을 통해 해당 함수를 그냥 종료합니다.

• if t[-1]=='A':    dfs(t[:-1]) 이 부분은 t 리스트의 마지막이 "A"라면, 이를 제외하고 재귀 호출을 하는 것입니다.
• if t[0]=='B':    dfs(t[1:][::-1]) 이 부분은 t 리스트의 첫 번째가 "B"라면, 이를 제외하고 뒤집어서 재귀 호출을 하는 것입니다.

이렇게 되면 t 리스트에서 해당 규칙을 반대로 적용해가며 S를 만드는 경우의 수들을 탐색하며 재귀 호출이 일어나게 됩니다. S를 만들게 되는 경우는 1을 출력하고 코드 자체를 종료시켜 버립니다.

 

3) 함수 호출

dfs(T)
print(0)

* 코드 설명

dfs(T)를 호출하면 위 함수가 호출되어 T(리스트)로 부터 S(리스트)가 만들어지는지 규칙을 반대로 적용하며 찾아갑니다. 만약 함수 중간의 1을 출력하는 부분을 만나지 않았다면, T에서 규칙을 반대로 적용한 것을 다 해봤는데도 S가 되지 않았다는 것을 의미하고, S가 T가 될 수 없다는 것을 의미하므로, 0을 출력하고 코드를 종료합니다.

5. 느낀 점

문자열 S를 문자열 T로 바꾸는 게 아니라, 문자열 T에서 규칙을 반대로 적용하여 S를 만드는 게, 수렴적으로 모든 경우를 탐색한다는 아이디어를 떠올리면 쉽게 풀 수 있는 문제입니다. 이 발상은 정말 어려웠던 것 같습니다. 어떻게 하면 S를 T로 만들 수 있을까.. 경우의 수가 너무 많은데라고 오랜 시간 고민하다가, 다른 풀이를 보고서야, "아 반대로 하는거구나"를 알았습니다. 

 

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

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