1722 Minimize Hamming Distance After Swap Operations

 

 

source를 조합해서 만드는 배열들과의 target 사이의 Hamming Distance들 중, 최솟값을 찾는 문제이다.

 

얼마나 Swap 연산을 수행하던지 상관없기에 source의 각 위치에서 DFS를 통해 target에서 가능한 모든 부분을 

방문하고, 방문하지 못한 위치들의 수가 Minimum Hamming Distance가 된다.

 

그리고 이 문제에서는 target의 원소가 중복될 수 있으므로 방문 여부를 확인할 때 인덱스를 이용했으며, Hamming Distance를 구할 때에는 Unordered map을 이용했다.

 

여담이지만, 이거 난이도가 왜 Medium인지 모르겠다. 보통 DFS 문제처럼 직관적으로 풀리면 모르겠는데, 그것도 아니고

중복되는 원소도 있고 Hard가 적당한거 같은데 Discuss 보니까 Union-Find로 풀었던데 DFS로 푸는 게 아니라

Union-Find로 풀었으면 쉬웠을려나, 아무튼 꾸준히 PS 해야겠다.

 

 

C++

class Solution {
public:
    vector<vector<int>> edges;
    vector<bool> visited;
    
    void dfs(int index, vector<int>& source, vector<int>& target, unordered_map<int, int>& cnts){
        
        visited[index] = true;
        
        ++cnts[source[index]];
        --cnts[target[index]];
        
        for(auto v : edges[index])
            if (!visited[v])
                dfs(v, source, target, cnts);
    }
    
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        const int n = source.size();
        edges = vector<vector<int>>(n);
        visited = vector<bool>(n);
        
        for(auto vec : allowedSwaps){
            edges[vec[0]].push_back(vec[1]);
            edges[vec[1]].push_back(vec[0]);
        }
        
        
        int res{};
        
        for(int i = 0; i < n; ++i){
            if (!visited[i]){
                unordered_map<int, int> cnts;
                dfs(i, source, target, cnts);
                for (auto [k, v] : cnts)
                    if (v > 0)
                        res += v;
            }
        }
        
        
        return res;
    }
};

Python

class Solution:
    def __init__(self):
        self.edges = None
        self.visited = None
        
    def dfs(self, index, source, target, cnts):
        self.visited[index] = True
        if source[index] in cnts.keys():
            cnts[source[index]] = cnts[source[index]] + 1
        else:
            cnts[source[index]] = 1
        if target[index] in cnts.keys():
            cnts[target[index]] = cnts[target[index]] - 1
        else:
            cnts[target[index]] = -1
        
        for v in self.edges[index]:
            if not self.visited[v]:
                self.dfs(v, source, target, cnts)
    
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n = len(source)
        self.edges = [[] for _ in range(n)]
        self.visited = [False for _ in range(n)]
        
        
        for vec in allowedSwaps:
            self.edges[vec[0]].append(vec[1])
            self.edges[vec[1]].append(vec[0])
        
        res = 0
        
        for i in range(n):
            if not self.visited[i]:
                cnts = {}
                self.dfs(i, source, target, cnts)
                for v in cnts.values():
                    if v > 0:
                        res = res + v
        
        return res