[LeetCode] 990 | Satisfiability of Equality Equations | Python

---

문제 링크: https://leetcode.com/problems/satisfiability-of-equality-equations/

---

문제

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

---

조건

• 1 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] is a lowercase letter.
• equations[i][1] is either '=' or '!'.
• equations[i][2] is '='.
• equations[i][3] is a lowercase letter.

---

내 풀이

equations에서 '=='에 해당하는 등식을 equal이라는 dictionary에 저장한다.

Queue를 이용해 equal을 graph라는 dictionary로 바꿔서 linked list처럼 사용한다.

다시 equations들을 보면서 '!='에 해당하는 식이 graph에 있다면 이는 possible한 식이 아니므로 False를 리턴한다.

---

코드

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        equal = defaultdict(list)
        
        for equation in equations:
            first, second = equation[0], equation[-1]
            if equation[1] == '=':
                equal[first].append(second)
                equal[second].append(first)
        
        graph = defaultdict(list)
        keys = list(equal.keys())
        
        for key in keys:
            queue = [key]
            visited = set()
            
            while len(queue) > 0:
                cur_key = queue.pop(0)
                
                if cur_key not in visited:
                    visited.add(cur_key)
                    graph[key] += cur_key
                    
                    for var in equal[cur_key]:
                        queue.append(var)
        
        for equation in equations:
            first, second = equation[0], equation[-1]
            if equation[1] == '!':
                if first == second:
                    return False
                elif first in graph[second]:
                    return False
                elif second in graph[first]:
                    return False
                
        return True