[위상 정렬] 269. Alien Dictionary ★★★★★

269. Alien Dictionary

 

🔍 문제 설명 (한 줄씩 해석)

There is a new alien language that uses the English alphabet.
→ 새로운 외계 언어가 있는데, 영어 알파벳을 사용합니다.

However, the order of the letters is unknown to you.
→ 하지만, 그 알파벳의 순서는 당신에게 알려지지 않았습니다.

You are given a list of strings words from the alien language's dictionary.
→ 외계 언어 사전에 등장하는 단어들이 정렬된 리스트 words로 주어집니다.

Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.
→ 이 words 리스트는 외계어의 알파벳 순서를 기준으로 사전순 정렬되어 있다고 주장됩니다.

If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".
→ 만약 이 정렬이 어떤 알파벳 순서로도 성립할 수 없다면, "" (빈 문자열)을 반환하세요.

Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules.
→ 그렇지 않다면, 외계어에서의 알파벳 순서대로 정렬된 모든 고유 문자를 문자열로 반환하세요.

If there are multiple solutions, return any of them.
→ 가능한 순서가 여러 개일 경우, 그 중 아무거나 하나 반환해도 됩니다.

---

✅ 문제 핵심 요약

• words 리스트는 외계어 기준으로 사전순 정렬되어 있어야 함
• 이 정렬을 통해 알파벳 간의 순서 관계를 유추하고,
• 가능한 순서가 있으면 알파벳 순서를 문자열로 반환하고,
• 불가능하면 빈 문자열 "" 반환

---

🧠 해결 아이디어

이건 전형적인 위상 정렬(Topological Sort) 문제입니다.

👣 풀이 순서

1. 모든 문자 노드 등록: 단어에 등장하는 모든 고유 문자 수집
2. 문자 간의 순서 관계 유도:
   • words[i] 와 words[i+1] 비교
   • 처음으로 다른 문자가 발견되면 → 그 문자의 순서가 정해짐 (a → b)
   • ex) "wrt" vs "wrf" → 't' → 'f'
3. 그래프 만들고 위상 정렬 수행
4. 사이클이 있으면 → 정렬 불가 → "" 반환
5. 정렬 성공 시, 정렬된 문자들을 하나의 문자열로 반환

1) DFS 기반 위상정렬

def alienOrderDFS(self, words: List[str]) -> str:
    # 1. 모든 고유 문자 수집
    graph = defaultdict(list)
    all_chars = set("".join(words))

    # 2. 문자 간 순서 유도
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i+1]
        min_len = min(len(w1), len(w2))
        if w1.startswith(w2) and len(w1) > len(w2):
            return ""  # 예외 케이스: 사전순 정렬이 안 된 경우
        for j in range(min_len):
            if w1[j] != w2[j]:
                graph[w1[j]].append(w2[j])
                break

    # 3. DFS 기반 위상 정렬
    visited = set()
    visiting = set()
    result = []

    def dfs(c):
        if c in visiting:
            return False  # 사이클
        if c in visited:
            return True

        visiting.add(c)
        for nei in graph[c]:
            if not dfs(nei):
                return False
        visiting.remove(c)
        visited.add(c)
        result.append(c)
        return True

    for c in all_chars:
        if c not in visited:
            if not dfs(c):
                return ""

    return "".join(reversed(result))

 

2) 칸 알고리즘 기반 ..BFS

def alienOrderBFS(self, words: List[str]) -> str:
    # 1. 모든 고유 문자 수집 및 진입차수 초기화
    graph = defaultdict(list)
    indegree = {c: 0 for word in words for c in word}

    # 2. 문자 간 순서 유도
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i+1]
        min_len = min(len(w1), len(w2))
        if w1.startswith(w2) and len(w1) > len(w2):
            return ""
        for j in range(min_len):
            if w1[j] != w2[j]:
                graph[w1[j]].append(w2[j])
                indegree[w2[j]] += 1
                break

    # 3. BFS (Kahn's Algorithm)
    queue = deque([c for c in indegree if indegree[c] == 0])
    result = []

    while queue:
        c = queue.popleft()
        result.append(c)
        for nei in graph[c]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    if len(result) < len(indegree):
        return ""  # 사이클 존재
    return "".join(result)