[python] algospot WORDCHAIN

문제

-> 문제 링크 : https://algospot.com/judge/problem/read/WORDCHAIN

algospot.com :: WORDCHAIN

 

문제풀이

이 문제의 핵심은 그래프를 어떤 식으로 만드느냐에 있다.

1. 정점이 각각의 단어들이 되고, 끝말잇기가 가능한 단어들끼리 잇는 방법이 있고,

2. 정점을 각 단어의 시작 알파벳과 끝 알파벳으로 두고 간선을 시작 알파벳에서 끝 알파벳 방향으로 잇는 방법이 있다.

 

1번 방법을 이용해서 풀려면 모든 정점을 한 번씩만 지나는 경로를 찾아야 한다.

이 문제는 해밀토니안 경로라고 부르며 최선의 알고리즘이 조합 탐색으로 최악의 경우에 O(n!)의 시간 복잡도가 나온다.

 

그러므로 2번 방법을 이용해 모든 간선을 한번씩만 지나는 경로를 찾는 문제인 오일러 트레일, 서킷을 찾는 문제로 해결해야 한다.

이 방법을 사용하면 O(V*E)의 시간복잡도로 문제를 해결할 수 있다.

- 오일러 트레일 : 모든 간선을 한번씩만 지나 시작 정점과 다른 정점에서 끝나는 경로

- 오일러 서킷 : 모든 간선을 한번씩만 지나 시작 정점으로 되돌아오는 경로

 

방향 그래프에서 오일러 서킷의 기본 전제는 각 정점에 들어오는 간선과 나가는 간선의 개수가 같아야 한다. 

이 조건이 만족하게 되면 그래프의 어느 정점에서 시작하더라도 오일러 서킷이 존재한다.

그리고 오일러 트레일의 전제 조건은 시작 정점은 나가는 간선의 개수가 들어오는 간선의 개수보다 1개 많아야 하고, 

끝 정점은 들어오는 간선의 개수가 나가는 간선의 개수보다 1개 많아야 한다. 그러면서 나머지 정점에서는 나가는 간선의 개수와 들어오는 간선의 개수가 같아야 한다. 이 조건이 만족하게 되면 시작 정점에서 시작해 끝 정점에서 끝나는 오일러 트레일이 존재한다.

 

문제를 해결하기 위해서는 먼저 입력값을 받아 그래프를 만들어 오일러 서킷이나 트레일이 존재하는지 판단해야 한다.

만약 오일러 서킷이 존재한다면 아무 정점에서나 시작하면 되고,

오일러 트레일이 존재한다면 시작 정점을 찾아 그 정점에서 시작하면 된다.

 

오일러 경로를 찾는 알고리즘은 dfs로 구현이 가능하다.

dfs의 입력 파라미터를 탐색하고자 하는 다음 정점과 현재 정점과 다음 정점을 잇는 간선의 가중치로 받는다.

( 가중치라고 말했지만 이 문제에서는 시작 알파벳과 끝 알파벳을 잇는 단어가 된다 )

dfs 내부에서는 반복문을 통해 현재 정점에서 존재하는 모든 간선에 접근한다.

간선이 존재한다면 그 간선을 삭제하면서 다음 정점과 간선의 가중치로 dfs를 재귀 호출한다.

그리고 재귀 함수가 끝나는 시점에 현재 정점을 도착지로 하는 간선의 가중치를 기록한다.

 

모든 간선을 탐색하고 재귀가 완료된 뒤 기록한 간선의 가중치를 뒤집어주면 오일러 경로가 만들어진다.

 

코드

import sys
import copy

def dfs(vertex, word) :

    while graph[vertex] :
        next_vertex, next_word = graph[vertex].pop()
        dfs(next_vertex, next_word)

    answer.append(word)


T = int(sys.stdin.readline().rstrip())

for _ in range(T) :
    N = int(sys.stdin.readline().rstrip())
    words = {}
    graph = {}
    in_edge = {}
    out_edge = {}
    visited = {}

    for alphabet in 'abcdefghijklmnopqrstuvwxyz' :
        graph[alphabet] = []
        in_edge[alphabet] = 0
        out_edge[alphabet] = 0

    for _ in range(N) :
        word = sys.stdin.readline().rstrip()
        graph[word[0]].append((word[-1],word))
        in_edge[word[-1]] += 1
        out_edge[word[0]] += 1

    answer = []

    candidates = []
    for alphabet in 'abcdefghijklmnopqrstuvwxyz' :
        if in_edge[alphabet] != out_edge[alphabet] :
            candidates.append(alphabet)

	# 오일러 트레일
    if len(candidates) == 2 :
        start = None
        end = None

        for alphabet in candidates:
            if in_edge[alphabet]+1 == out_edge[alphabet] :
                start = alphabet

            if in_edge[alphabet] == out_edge[alphabet]+1 :
                end = alphabet

        if start and end :
            dfs(start,"")

	# 오일러 서킷
    elif len(candidates) == 0 :
        for alphabet in 'abcdefghijklmnopqrstuvwxyz' :
            if in_edge[alphabet] is not 0 :
                dfs(alphabet,"")
                break


    if answer :
        print( " ".join(reversed(answer)).strip())
    else :
        print("IMPOSSIBLE")

 

초기 접근 방식과 오답의 원인

오일러 서킷과 오일러 트레일의 기본 조건을 제대로 알지 못했고,  경로를 찾는 알고리즘을 짜는 방법을 몰랐다.

 

 

코드에 잘못된 부분이나 개선 사항을 댓글로 알려주시면 감사하겠습니다.