Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬(Python)으로 단어들이 연결되어 원을 이루는지 확인하는 프로그램

문제 정의

단어 목록이 주어졌다고 가정해 보겠습니다. 이때 주어진 단어들을 서로 연결하여 하나의 원(circle) 형태로 만들 수 있는지 확인해야 합니다. 단어 A가 다른 단어 B 앞에 배치될 수 있는 유일한 조건은 A의 마지막 문자가 B의 첫 번째 문자와 동일할 때입니다. 또한 모든 단어를 빠짐없이 사용해야 하며, 각 단어는 정확히 한 번만 사용할 수 있습니다.

예를 들어 입력이 다음과 같다면,

["ant", "dog", "tamarind", "nausea", "gun"]

출력 결과는 True가 됩니다.

알고리즘 접근 방식

이 문제는 그래프 이론의 오일러 회로(Eulerian Circuit) 개념과 밀접한 관련이 있습니다. 각 단어를 '첫 글자 노드'에서 '마지막 글자 노드'로 향하는 간선으로 생각하면, 모든 간선(단어)을 정확히 한 번씩 사용해 원을 이루는 경로가 존재하는지 확인하는 문제가 됩니다.

이를 해결하기 위해 다음 자료구조를 준비합니다.

  • graph: 각 시작 문자에서 도달 가능한 끝 문자들을 저장하는 인접 리스트(키-값 구조)

  • seen: 방문한 노드를 추적하는 집합(set)

  • inDegree: 각 문자로 들어오는 간선의 수

  • outDegree: 각 문자에서 나가는 간선의 수

그다음 아래 순서대로 처리합니다.

  1. 각 단어에 대해 시작 문자(start)와 끝 문자(end)를 추출합니다.

  2. graph[start]에 end를 추가하고, outDegree[start]와 inDegree[end]를 각각 1씩 증가시킵니다.

  3. 모든 노드를 검사하면서 진출 차수와 진입 차수가 일치하지 않는 노드가 있으면 False를 반환합니다.

  4. 첫 번째 단어의 첫 문자에서 DFS 탐색을 시작합니다.

  5. 방문한 노드 수(seen)가 그래프의 전체 노드 수(graph)와 같으면 True, 그렇지 않으면 False를 반환합니다.

DFS 함수의 역할

  • 현재 노드를 seen 집합에 추가합니다.

  • graph[node]에 있는 각 자식 노드에 대해, 아직 방문하지 않았다면 재귀적으로 dfs(child)를 호출합니다.

차수 조건(진입 차수 = 진출 차수)과 연결성 조건(DFS로 전체 노드 방문 가능)을 모두 만족해야 단어들이 하나의 원을 이룰 수 있습니다.

구현 예제

아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.

import collections

class Solution:
    def solve(self, words):
        self.graph = collections.defaultdict(list)
        self.seen = set()
        inDegree = collections.Counter()
        outDegree = collections.Counter()

        for word in words:
            start = word[0]
            end = word[-1]
            self.graph[start].append(end)
            outDegree[start] += 1
            inDegree[end] += 1

        for node in outDegree:
            if outDegree[node] != inDegree[node]:
                return False

        self.dfs(words[0][0])
        return len(self.seen) == len(self.graph)

    def dfs(self, node):
        self.seen.add(node)
        for child in self.graph[node]:
            if child not in self.seen:
                self.dfs(child)

ob = Solution()
print(ob.solve(["ant", "dog", "tamarind", "nausea", "gun"]))

입력

["ant", "dog", "tamarind", "nausea", "gun"]

출력

True

동작 원리 설명

예제 입력에서 각 단어는 다음과 같이 연결됩니다.

ant → tamarind → dog → gun → nausea → ant

'ant'의 마지막 글자 't'가 'tamarind'의 첫 글자와 일치하고, 'tamarind'의 마지막 글자 'd'가 'dog'의 첫 글자와, 'dog'의 마지막 글자 'g'가 'gun'의 첫 글자와, 'gun'의 마지막 글자 'n'이 'nausea'의 첫 글자와 각각 연결됩니다. 마지막으로 'nausea'의 마지막 글자 'a'가 다시 'ant'의 첫 글자와 이어지면서 완전한 원을 형성합니다. 따라서 결과는 True입니다.