[백준 16500][파이썬] 문자열 판별 (dfs)

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

16500번: 문자열 판별

 

이 문제는 A에 속한 문자열들 중 적절히 골라서 S를 만드는 문제이다.

 

문자열은 중복해서 고를 수 있고 공백없이 이어붙여야 한다.

 

가장 먼저 A에 속한 문자열들일 각각 S에 포함되어 있는지 확인해야 한다.

 

포함되어 있지 않다면 그 문자열은 S를 만드는데 사용할 수 없다.

 

만약 포함되어 있다고 한다면 그 문자열이 S를 만드는데 들어가는 위치는 반드시 정해져있다.

 

위의 예시에서 본다면 software는 반드시 S의 첫 번째 위치부터 8번째 위치까지로 고정되어있다.

 

만약 S가 softwaresoftware 였다면 software를 사용할 때 들어갈 위치는 (1~8)과 (9~16) 둘 중 하나로 정해져있다.

 

 그리고 A에 포함된 문자열들을 공백 없이 이어붙여야 한다.

 

S가 softwarecontest이고 A는 [ softwarecon, warecontest ]라고 한다면 A의 문자열을 사용해서 S를 만들 수 없다.

 

반드시 공백 없이 이어붙여야 하기 때문이다.

 

 이러한 문제의 특성을 고려하면 이 문제는 비용 없는 방향 그래프로 해결할 수 있다.

 

노드 a와 노드 b가 연결되어있다는 뜻은 문자열 S의 인덱스 a에서부터 인덱스 b까지 해당하는 부분 문자열이 A에 속해있다는 뜻이다.

 

즉 S가 softwarecontest이고 A가 [ software, contest]라면 아래와 같은 그래프가 만들어질 것이다.

가장 처음 인덱스인 0부터 끝 인덱스인 15까지 탐색을 진행하면 된다.

 

그런데 위 그래프에서는 0에서 15까지 도달할 수가 없지만 실제로는 software와 contest를 이어붙여서 S를 만들 수가 있다.

 

그래서 A에 속한 문자열들 각각 끝 위치에 1을 더해줘야 한다.

 

그래야 노드들을 이어줄 수 있다. 위 그래프를 이러한 방식으로 바꿔보면 다음과 같다.

이제 문제에서 요구하는 정답을 그래프 탐색을 통해서 구할 수 있다.

 

참고로 이 부분 문자열이 어떤 문자열인지는 알 필요가 없다. 

 

문제의 답은 A의 문자열들을 사용하여 S 생성 여부를 판단하는 것이기 때문이다.

 

먼저 그래프를 구하는 코드이다.

import sys
from collections import defaultdict
input=sys.stdin.readline
S=input().rstrip()
n=int(input())
A=[input().rstrip() for _ in range(n)]
#graph[i]==j의 의미는 S[i:j+1]이 A에 포함된다는 뜻
# graph=[[] for _ in range(len(S)+1)]
graph=defaultdict(lambda : []) 
def make_graph(x): # A에 속한 문자열 x가 S에 포함되면 그래프 생성
    for i in range(len(S)-len(x)+1):
        if S[i:i+len(x)]==x: # 포함된다면
            graph[i].append(i+len(x)) # 끝 칸 하나 늘려서 저장
for i in A:
    make_graph(i)

A 속한 문자열 하나하나마다 전부 S와 비교를 해서 일치하는 부분 문자열이 존재한다면 해당 처음 인덱스와 끝 인덱스를 기준으로 간선을 추가하고 있다.

 

이 다음은 그래프를 탐색하기만 하면 된다. 목적지에 도달하기만 하면 되니까 DFS를 통해 구현했다.

 

#그래프가 완성됐으니 dfs 시작
visited=[False]*(len(S)+1) # 노드 방문 여부
start_node=0 # 출발 노드
end_node=len(S) # 도착 노드
def dfs(x):
    visited[x]=True
    if x==end_node: # 목적지에 도착했다면
        print(1)
        exit()
    for i in graph[x]: #연결된 노드 방문
        if not visited[i]: # 방문하지 않은 노드면 dfs 다시 시작
            dfs(i)

 

<최종 코드>

import sys
from collections import defaultdict
input=sys.stdin.readline
S=input().rstrip()
n=int(input())
A=[input().rstrip() for _ in range(n)]
#graph[i]==j의 의미는 S[i:j+1]이 A에 포함된다는 뜻
# graph=[[] for _ in range(len(S)+1)]
graph=defaultdict(lambda : []) 
def make_graph(x): # A에 속한 문자열 x가 S에 포함되면 그래프 생성
    for i in range(len(S)-len(x)+1):
        if S[i:i+len(x)]==x: # 포함된다면
            graph[i].append(i+len(x)) # 끝 칸 하나 늘려서 저장
for i in A:
    make_graph(i)
#그래프가 완성됐으니 dfs 시작
visited=[False]*(len(S)+1) # 노드 방문 여부
start_node=0 # 출발 노드
end_node=len(S) # 도착 노드
def dfs(x):
    visited[x]=True
    if x==end_node: # 목적지에 도착했다면
        print(1)
        exit()
    for i in graph[x]: #연결된 노드 방문
        if not visited[i]: # 방문하지 않은 노드면 dfs 다시 시작
            dfs(i)
dfs(0)
print(0)