백준 3178 - 코코스 (Python)

문제 정보

• https://www.acmicpc.net/problem/24782
• 백트래킹, 브루트포스

---

문제 정리

길이가 2K인 문자열 N개가 주어진다.
그래프의 정점에 글자를 하나씩 할당할 때, 아래 조건을 만족하는 그래프의 정점 개수로 가능한 최소값을 구하는 문제이다.

• 첫 정점의 in-degree는 0이다.
• 다음 K-1개 정점의 in-degree는 1이다.
• 다음 K-1개 정점의 out-degree는 1이다.
• 마지막 정점의 out-degree는 0이다.

---

풀이

• 딱 보면 Trie를 사용해야 할 것 같이 생겼다.

• 앞의 K개 문자는 분할될 수만 있고, 뒤의 K개 문자는 합쳐질 수만 있으니 앞의 K개 문자만 따로 빼서 리스트에 모아두고, 뒤의 K개 문자도 따로 빼서 역순으로 뒤집어 다른 리스트에 모아두자.

• 각 리스트에 저장된 단어를 Trie에 넣고 정점 개수를 세주면 된다.
  였으면 좋겠지만 MLE가 발생했다...

• 사실 정점 개수만 세주면 되므로 굳이 Trie가 필요하지 않다.

• Trie에서 분할이 되는 부분은 기존에 Trie에 저장된 문자열과 다른 문자가 나타날 때이므로, 이 부분을 체크해주면 된다.

• 문자열을 사전순으로 정렬해주고, 인접한 두 문자열을 앞에서부터 비교하면서 문자가 달라지는 부분을 찾는다.
  이 부분 이후로는 같은 부분이 생겨도 다른 정점으로 분리되니 길이만큼 정점 개수를 더해주면 된다.

---

후기

기여창 보니 MLE가 파이썬이라 발생한 것 같기도 하고...

---

코드

# 백준 3178

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def countNode(N, K, word):
    result = K
    word.sort()
    for i in range(1, N):
        connect = True
        for j in range(K):
            if connect == False:
                result += K-j
                break
            elif word[i-1][j] != word[i][j]:
                result += 1
                connect = False

    return result


def solve(N, K, word1, word2):
    result = countNode(N, K, word1)
    result += countNode(N, K, word2)

    return result


def main():
    N, K = map(int, input().split())
    word1 = []
    word2 = []
    for _ in range(N):
        w = input().decode().strip()
        word1.append(w[:K])
        word2.append(w[K:][::-1])


    print(solve(N, K, word1, word2))


main()