<Medium> Satisfiability of Equality Equations (LeetCode : C#)

https://leetcode.com/problems/satisfiability-of-equality-equations/

📕 문제 설명

다음의 식들로 이루어진 배열이 주어질 때 모든 주어진 식들을 만족하면서 variable을 대입하는 것이 가능한지에 대한 여부 반환

식은 "xi==yi" 또는 "xi!=yi"로 이루어지며 각 변수는 하나의 소문자이다.

• Input
  equations 배열
• Output
  모든 equations 만족하는 변수 존재 여부

예제

풀이

먼저 같아야하는 케이스 돌면서 같은 값을 가리키게 만든 다음 달라야하는 케이스를 돌면서 만약 같은 값이 나오면 false 바로 return 하도록

public class Solution {
    public bool EquationsPossible(string[] equations) {
        int[] parent = new int[26];
        for(int i = 0; i < 26; i++) parent[i] = i;
        
        for(int i = 0; i < equations.Length; i++) 
        {
            if(equations[i][1] == '=') // 같아야 하므로 
            {
                int parentA = FindParent(equations[i][0] - 'a', parent);
                int parentB = FindParent(equations[i][3] - 'a', parent);
                if(parentA != parentB) 
                {
                    parent[parentB] = parentA; // parent 통일시켜주기
                }
            }
        }

        for(int i = 0; i < equations.Length; i++) 
        {
            if(equations[i][1] == '!') {
                int parentA = FindParent(equations[i][0] - 'a', parent);
                int parentB = FindParent(equations[i][3] - 'a', parent);
                if(parentA == parentB) return false; // 같다면 식 만족 불가능
            }
        }

        return true;
    }

    private int FindParent(int num, int[] parent) {
        if(parent[num] == num) return num;
        parent[num] = FindParent(parent[num], parent);
        return parent[num]; 
    }
}

결과