Category
알고리즘  백트래킹

[16500] 문자열 판별

by Hwang

문제

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

풀이

재귀 호출로 가능한 모든 경우의 수를 찾아 문자열을 만들 수 있는지 확인하는 방법으로 풀었습니다.

그러나 단순히 경우의 수를 모두 찾아준다면 시간초과로 인해 풀이가 불가능합니다. 따라서 방문처리를 해줘 이미 탐색을 마친 경우는 생략해주는 방식으로 풀어야합니다.

배열 visited[i]는 i 번까지 도달했는지를 의미합니다.

import sys

S = sys.stdin.readline().strip()
N = int(sys.stdin.readline())
words = [sys.stdin.readline().strip() for _ in range(N)]
visited = [False] * (len(S) + 1)

def find(current, index):
    if visited[index]:
        return
    visited[index] = True
    if current == S:
        return
    for word in words:
        if len(current) + len(word) > len(S):
            continue
        if S[index: index + len(word)] == word:
            find(current + word, index + len(word))
    return

find('', 0)
print(1 if visited[-1] else 0)


 Comment