[BOJ] 16500 - 문자열 판별 (Python)

 

 

아이디어

 

문자열 내에서 단어의 시작과 끝 인덱스를 그래프로 표현하고 BFS로 문자열을 만들 수 있는지 확인한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    S = input().rstrip()
    M = len(S)
    N = int(input())
    graph = [[] for _ in range(101)]
    for _ in range(N):
        a = input().rstrip()
        l = len(a)
        idx = S.find(a, 0)
        while idx >= 0:
            graph[idx].append(idx+l)
            idx = S.find(a, idx+l)
    visited = [0]*101
    visited[0] = 1
    stack = [0]
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if visited[v] == 0:
                visited[v] = 1
                stack.append(v)
    print(visited[M])

solution()