[BOJ] 1195 : 킥다운 [브루트포스](Python)

문제 링크

https://www.acmicpc.net/problem/1195

1195번: 킥다운

소스 코드

a = input()
b = input()

answer = len(a) + len(b) # 최악의 경우
# 길이가 긴 것을 a, 짧은 것을 b로 설정
if len(a) < len(b):
    a,b = b,a
gap = len(a) - len(b)

# 길이가 짧은 것이 왼쪽에 길게 늘어지는 경우
# 000002112112112
# 221211200000000
for zero in range(len(b)-1,0,-1):
    # 0의 개수를 줄이며 길이가 동일한 문자열 쌍을 유지
    tmp_a = '0' * zero + a
    tmp_b = b + '0' * (zero+gap)
    
    flag = True # 이상 탐지 flag
    for up,down in zip(tmp_a,tmp_b):
        # 튀어나온 부분이 겹치면 불가능한 case
        if up == '2' and down == '2':
            flag = False
            break
    if flag: # 이상이 발견되지 않은 경우라면 정답 갱신
        answer = min(answer,len(tmp_a))
    if answer == len(a): # 최소 길이가 중간에 발견되면 종료
        print(answer)
        exit(0)

# 길이가 짧은 것이 오른쪽에 길게 늘어지는 경우    
# 211211211200000
# 000000002212112
for zero in range(len(b)-1,0,-1):
    # 0의 개수를 줄이며 길이가 동일한 문자열 쌍을 유지
    tmp_a = a + zero * '0'
    tmp_b = (zero+gap) * '0' + b

    flag = True # 이상 탐지 flag
    for up,down in zip(tmp_a,tmp_b):
        # 튀어나온 부분이 겹치면 불가능한 case
        if up == '2' and down == '2':
            flag = False
            break
    if flag: # 이상이 발견되지 않은 경우라면 정답 갱신
        answer = min(answer,len(tmp_a))
    if answer == len(a): # 최소 길이가 중간에 발견되면 종료
        print(answer)
        exit(0)
# 두 문자열이 완전히 겹쳐 있는 경우
# 2112112112
# 0022121120
for zero in range(gap,-1,-1):
    # 0의 개수를 줄이며 길이가 동일한 문자열 쌍을 유지  
    tmp_a = a
    tmp_b = '0'*(gap-zero) + b + '0'*zero

    flag = True # 이상 탐지 flag
    for up,down in zip(tmp_a,tmp_b):
        # 튀어나온 부분이 겹치면 불가능한 case
        if up == '2' and down == '2':
            flag = False
            break
    if flag:
        answer = min(answer,len(tmp_a))
    if answer == len(a): # 최소 길이가 중간에 발견되면 종료
        print(answer)
        exit(0)
# 최소 길이가 중간에 발견되지 않은 case
print(answer)

 

해설

• 브루트포스, 완전탐색

문제 설명이 친절하지는 않아서 문제를 이해하기가 조금 어려웠던 것 같네요.

좋은 방법이 있는지는 모르겠지만 코드도 굉장히 지저분하게 작성해버렸습니다 🥲

 

코드의 주석에도 예시를 적어둔 것처럼 저는 크게 세 가지 유형으로 구분하고 각자 for문을 돌려 답을 구했습니다.

그전에 먼저 문제의 조건 중 가장 핵심적인 것을 떠올려보면 

 

1) '위의 블록과 아래의 블록이 둘 다 2인 경우는 불가능' 합니다.

둘 다 튀어나온 '이'에 해당하는 자리이기 때문에, 블록을 포개어 비교할 때 이런 경우는 아예 무시해야 합니다.

 

그래서 저는 이 조건에 해당하면 flag = False 로 변경하고, for문이 끝났을 때 flag가 True로 남아있는 경우에만 정답을 갱신하도록 했습니다.

 

2) min 함수로 정답 갱신

초기엔 정답을 두 문자열의 길이합으로 설정합니다.

만약 어떤 경우에도 두 블록이 겹칠 수가 없는 경우라면 아예 겹치지 않은 상태가 정답이 될 것이기 때문입니다.

 

탐색을 반복하는 동안에는 만약 두 블록이 겹치게 되고 어떤 문제도 발생하지 않은 경우 그 문자열의 길이를 정답과 비교하여 작은 것을 취합니다.

00002112112112
22121120000000

예를 들어 '길이가 짧은 것이 왼쪽으로 늘어지는 경우', 위처럼 빈 공간에는 0을 알맞게 채워 넣고 비교합니다.

이때 겹치는 부분에 2,2로 만나는 경우는 없으므로 위 경우 또한 정답이 될 가능성이 있습니다.

위 문자열의 길이는 14 이므로, 만약 기존에 anwer = 17 이었다면 min 함수를 통해 answer = 14로 갱신됩니다.

이 과정을 반복하면 되는데, 효율성을 위해 이 answer가 두 문자열 중 길이가 긴 것과 동일한 길이가 된다면 프로그램을 종료합니다.

 

최악의 경우엔 두 블록이 하나도 겹치지 않겠지만, 최선의 경우엔 두 블록이 온전히 겹칠 수 있을 것입니다.

이때는 길이가 긴 문자열의 길이가 곧 정답이 되므로 이를 비교해주는 것입니다.

 

3) 좌우에 적절한 개수의 '0'을 배치하여 동일한 길이의 문자열 유지

아마 직접 작성하지 않은 코드의 범위를 바로 이해하는 것은 쉽지 않을 것입니다.

따라서 직접 숫자를 쓰고 결과를 출력하며 비교해보시길 바랍니다.

 

저는 위에서 언급한 것처럼 세 가지 경우로 나눴습니다.

1. 길이가 짧은 것이 왼쪽으로 길게 늘어지는 경우

2. 두 문자열이 완전히 겹쳐 있는 경우

3. 길이가 짧은 것이 오른쪽으로 길게 늘어지는 경우

 

따라서 각 경우에 따라 두 문자열의 길이 차인 gap 변수와 문자열의 길이를 적절히 조합하여 0을 추가하고 두 문자열의 길이가 동일한 상태에서 비교할 수 있도록 해줍니다.

만약 두 문자열의 길이가 동일하게 세팅이 되지 않는다면 인덱스 에러가 발생할 가능성이 매우 높습니다.