[백준 30090] 백신 개발

문제 출처 : https://www.acmicpc.net/problem/30090

30090번: 백신 개발

이 문제는 제 1회 청소년 IT 경시대회 초등부 B번, 고등부 A번 문제 입니다.

겹치는 문자열을 이어 붙여 가장 짧은 문자열을 만드는 문제 입니다. 예제를 확인해보면 3개의 입력이 주어집니다.

RUST, VIRUS, STAND 입니다. 이 3개의 문자를 겹치는 부분을 하나로 만들어 잘 이어주면 VIRUSTAND 라는 문자열이 가장 짧은 문자열이 되고 이 문자열의 길이인 9를 출력하는 문제 입니다.

문제 이해하기

반드시 답이 존재하는 경우만 주어지기 때문에 문제에 있는 조건을 모두 만족하는 입력만 있습니다. 따라서 예외에 대해서 따로 고민하지 않아도 됩니다. 문자열의 수 N은 최대 9개이고, 문자열의 길이는 10 이하 입니다. 수가 작기 때문에 특별한 알고리즘을 사용할 필요 없이 하나하나 비교해도 충분 합니다.

두 문자열에서 중복되는 부분을 찾아 이어주는 것이 이 문제의 핵심 입니다. 두 문자열의 비교하는 방법을 생각해 보겠습니다. RUST와 VIRUS를 예를 들어 보겠습니다.

하나는 앞쪽을, 하나는 뒤쪽을 잘라주어야 합니다. 먼저 RUST의 전체 RUST와 VIRUS의 IRUS를 비교합니다.

두 값이 같지 않기 때문에 RUST의 RUS와 VIRUS의 RUS를 비교합니다.

이제 두 문자열이 같기 때문에 RUST의 RUS를 제외한 나머지 T를 VIRUS에 붙여 줍니다. 그럼 VIRUST가 됩니다. 이렇게 문자열을 만들어주고, 그 길이를 출력하여 가장 짧은 길이를 출력하면 됩니다.

길이를 전체에서 짧은 순서로 비교하였습니다. 거꾸로 R만 비교하고 다음에는 RU를 비교하면 안될까 하는 생각을 가질 수 있습니다. 하지만 이렇게 해서는 안됩니다. 왜냐하면 아래와 같은 비교를 한다고 하겠습니다.

여기서는 RRR을 비교해야 하는데 첫 비교부터 R과 R이 같기 때문에 더이상 비교를 안하고 넘어갈 수 있습니다. 이렇기 때문에 전체를 먼저 비교해야 정확한 길이를 알 수 있습니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력 받기

N = int(input())

arr = []
for _ in range(N):
    temp = input()
    arr.append(temp)

바이러스를 구성하는 문자열의 수 N을 입력 받습니다. 다음으로 N개의 줄에 걸쳐 바이러스를 구성하는 문자열을 받아 arr이라는 리스트에 저장 하였습니다.

출력하기

ans = 100
dfs(0, "")
print(ans)

정답이 들어있는 변수 ans의 초기값으로 100을 하였습니다. N이 10보다 작고, 문자열의 길이도 10 이하이기 때문에 정답의 최대값은 100을넘을수 없습니다. 백트래킹을 하기 위해 dfs 함수를 실행합니다. dfs 알고리즘 자체가 백트래킹과 비슷하게 동작하기 때문에 dfs 라는 함수명을 사용하고는 합니다.

dfs 함수에는 두개의 인자가 들어갑니다. 첫 번째 인자는 몇 번째 문자열인지 확인하기 위한 인덱스 입니다. 첫 번째 문자열을 확인하기 위해 0을 입력 하였습니다. 두 번째 인자는 지금까지 만들어진 바이러스 문자열 입니다. 처음에는 빈 문자열로 시작합니다.

dfs 함수를 모두 돌고 나면 ans 값이 정답으로 바뀌게 되고, ans를 출력하면 됩니다.

dfs 함수

visited = [False] * N
def dfs(depth, my_str):
    global ans
    if depth == N:
        ans = min(ans, len(my_str))
        return
    
    for i in range(N):
        if visited[i]:
            continue
        visited[i] = True
        nxt_str = make_str(arr[i], my_str)
        dfs(depth + 1, nxt_str)
        visited[i] = False

dfs 함수 입니다. 먼저 방문 확인을 위한 visited 리스트를 만들어 줍니다. 다음으로 ans값이 계속 변경되기 때문에 global로 지정해 놓습니다. ans 값을 global로 지정하지 않고 리턴값으로 한다면 재귀 함수가 전부 스택으로 쌓이게 됩니다. 그런 경우 쌓인 스택으로 인해 전체적으로 느려지기 때문에 백트래킹을 할 때면 리턴값을 안만드는 것이 프로그램을 더 빠르게 만드는 방법 입니다.

종료 조건

백트래킹이나 dfs 함수 실행시 재귀를 종료하는 종료조건이 필수적으로 들어가야 합니다. depth 가 N이 되었다는 것은 모든 문자열을 모두 확인했다는 뜻입니다. 따라서 이 때 문자열 my_str의 길이와 ans값을 비교하여 더 짧은 것으로 바꿔주고 프로그램을 종료합니다.

백 트래킹

반복하는 구간 입니다. 이미 방문한 곳이면 바로 넘어갑니다. 아직 방문을 하지 않았으면 방문 표시를 해줍니다. nxt_str은 두 문자열을 합쳐주는 부분 입니다. 이 함수에서 인자의 순서가 중요합니다. arr[i]와 my_str의 위치를 바꾸면 안됩니다.

make_str 함수로 만들어진 문자열로 다음 dfs 함수를 수행 합니다. 그리고 방문 했다는 표시를 제거합니다. 이렇게 해야 모든 경우를 다 따질 수 있습니다.

make_str

def make_str(A, B): 
    for i in range(len(A), -1, -1):
        start_A = A[:i]
        end_B = B[len(B) - i:]
        
        if start_A == end_B:
            result = B + A[i:]
            return result

이 문제의 핵심 make_str 입니다. 두 문자열을 가지고 비교합니다. A는 arr[i]의 값이 들어있고, B에는 my_str 값이 들어 있습니다. B에 있는 문자열은 여러개의 문자열이 합쳐졌다면 꽤나 길어져 있을 수 있습니다. 그래서 A와 B의 위치를 바꾸면 안된다는 것입니다.

가령 my_str의 길이가 50자가 넘었다고 하겠습니다. arr[i]는 10자 이하 입니다. 두 길이가 너무 많이 차이나면 len(B) - i 값이 10 - 50이 되어 -40이 되는 경우가 생길수도 있습니다. 따라서 B쪽에 my_str을 배치한 것입니다.

start_A 와 end_B를 i값으로 찾습니다. 위의 RUST를 예를 들면 RUST, RUS, RU, R 순서로 변하게 됩니다. VIRUS는 IRUS, RUS, US, S 순으로 변하게 됩니다. 이 때 두 값이 같은 RUS가 되는 경우 조건문에 들어가게 되고 result 값은 B인 VIRUS에 A[i:] 는 T이기 때문에 두 값을 합쳐 VIRUST가 되고 이 값을 리턴하게 됩니다.

전체 코드

전체 코드를 확인해 보겠습니다.

N = int(input())

arr = []
for _ in range(N):
    temp = input()
    arr.append(temp)

def make_str(A, B): 
    for i in range(len(A), -1, -1):
        start_A = A[:i]
        end_B = B[len(B) - i:]
        
        if start_A == end_B:
            result = B + A[i:]
            return result

ans = 10e9
visited = [False] * N
def dfs(depth, my_str):
    global ans
    if depth == N:
        ans = min(ans, len(my_str))
        return
    
    for i in range(N):
        if visited[i]:
            continue
        visited[i] = True
        nxt_str = make_str(arr[i], my_str)
        dfs(depth + 1, nxt_str)
        visited[i] = False
        
dfs(0, "")
print(ans)