문제 링크: https://www.acmicpc.net/problem/8913

Thumbnail: Photo by Finn (Unsplash)

백트래킹으로 가능한 모든 경우를 찾는 문제입니다!

풀이

백트래킹 (DFS)

​​백트래킹으로 가능한 모든 경우를 탐색해, 한 가지 경우라도 전체 문자열을 빈 문자열로 바꿀 수 있는지 찾아내면 됩니다.

전체 문자열의 길이는 최대 25자에 시간 제한은 2초(언어마다 조금씩 다릅니다.)이므로, 충분히 백트래킹으로 풀 수 있습니다.

백트래킹(DFS) 함수의 매개변수로 어떤 것을 사용할지 고민했는데, 현재 문자열의 각 그룹의 시작 인덱스와 끝 인덱스의 쌍을 매개변수로 사용했습니다.

이해의 편의를 위해, 타입 힌트가 적용된 코드를 첨부합니다.

• get_group_len 함수는 한 개의 그룹에 포함된 문자의 개수, 즉 그룹의 길이를 계산합니다.
• 각 그룹의 정보는 (시작 인덱스, 끝 인덱스)의 형태로 저장됩니다. 이때, 끝 인덱스는 마지막 문자의 인덱스 + 1에 해당합니다.
• DFS에서 다음 분기를 탐색할 때, 다음 조건을 고려합니다.
  • 그룹의 길이가 2 이상인가? (1개 문자로 구성된 그룹은 지울 수 없습니다.)
• 전체 문자열을 이루는 각 그룹을 하나씩 지워보며 DFS를 수행합니다.
  • 첫 그룹을 지우는 경우와 마지막 그룹을 지우는 경우는 모두 슬라이싱으로 간단하게 구현할 수 있습니다.
  • 그 외의 경우는, 제거된 그룹 양 옆의 그룹이 합쳐지게 되므로 합쳐진 그룹 및 이후 그룹의 인덱스를 갱신해줘야 합니다.
• 만약 문자열을 모두 지울 수 있는 경우를 찾았다면, 그 즉시 DFS를 종료합니다.

GroupInfo = tuple[int, int]
Groups = list[GroupInfo]

def get_group_len(part: GroupInfo) -> int:
    return part[1] - part[0]

def dfs(string_groups: Groups) -> bool:
    """
    현재 분기의 문자열 그룹 정보를 토대로 백트래킹을 진행합니다.
    
    Arguments:
        string_groups : 현재 분기의 문자열을 구성하는 각 그룹의 정보(시작과 끝 인덱스를 나타내는 2개의 정수 쌍)를 담은 배열입니다.
    """
    if len(string_groups) == 1: # end of dfs
        res = string_groups[0][1] - string_groups[0][0] >= 2 # return whether we can remove last part.
        return res
    
    res = False
    # Case 1. Remove first elem
    if get_group_len(string_groups[0]) >= 2:
        res = dfs([*string_groups[1:]])
    # Case 2. Remove middle elem
    for gruop_idx in range(1, len(string_groups) - 1):
        diff = get_group_len(string_groups[gruop_idx])
        if diff < 2:
            continue
        left = [*string_groups[:gruop_idx - 1]]
        mid = (string_groups[gruop_idx - 1][0], string_groups[gruop_idx + 1][1] - diff)
        left.append(mid)
        if gruop_idx < len(string_groups) - 2:
            left.extend(map(lambda p: (p[0] - diff, p[1] - diff), string_groups[gruop_idx+2:]))
        res = dfs(left)
        if res:
            break
    # Case 3. Remove last elem
    if not res and get_group_len(string_groups[-1]) >= 2:
        res = dfs([*string_groups[:-1]])
    return res

전체 코드

input = open(0).readline

GroupInfo = tuple[int, int]
Groups = list[GroupInfo]

def get_group_len(part: GroupInfo) -> int:
    return part[1] - part[0]

def dfs(string_groups: Groups) -> bool:
    """
    Backtracking (DFS with condition) using string's group information.
    
    Arguments:
        string_groups (list[tuple[int, int]]): list of group info(tuple of two integers: start & end index)
    """
    if len(string_groups) == 1: # end of dfs
        res = string_groups[0][1] - string_groups[0][0] >= 2 # return whether we can remove last part.
        return res
    
    res = False
    # Case 1. Remove first elem
    if get_group_len(string_groups[0]) >= 2:
        res = dfs([*string_groups[1:]])
    # Case 2. Remove middle elem
    for gruop_idx in range(1, len(string_groups) - 1):
        diff = get_group_len(string_groups[gruop_idx])
        if diff < 2:
            continue
        left = [*string_groups[:gruop_idx - 1]]
        mid = (string_groups[gruop_idx - 1][0], string_groups[gruop_idx + 1][1] - diff)
        left.append(mid)
        if gruop_idx < len(string_groups) - 2:
            left.extend(map(lambda p: (p[0] - diff, p[1] - diff), string_groups[gruop_idx+2:]))
        res = dfs(left)
        if res:
            break
    # Case 3. Remove last elem
    if not res and get_group_len(string_groups[-1]) >= 2:
        res = dfs([*string_groups[:-1]])
    return res

for _ in range(int(input())):
    orig_group: str = input().strip()
    groups: Groups = []
    prev: str = orig_group[0]
    prev_start: int = 0
    for idx in range(1, len(orig_group)):
        if orig_group[idx] != prev:
            groups.append((prev_start, idx)) # [start, end)
            prev_start = idx
            prev = orig_group[idx]
    groups.append((prev_start, len(orig_group))) # last part.
    res = dfs(groups)
    print("1" if res else "0")