LeetCode 1722 Minimize Hamming Distance After Swap Operations

접근

  1. 연결되어 있는 인덱스 정보를 담을 그래프 graph, 방문 여부 visited 를 초기화한다.
  2. iteration 돌면서 각 i 가 아직 방문 안했다면 bfs로 연결된 인덱스를 모두 찾는다.
  3. 연결된 인덱스를 lst 에 담고 subset 에는 해당하는 인덱스의 source 값을 담는다.
  4. bfs 가 끝나면 lst 의 모든 원소에 대해 target[i] 가 subset 에 있는지 찾는다.
  5. target[i] 가 subset 에 있다면 스왑으로 distance 를 0으로 만들 수 있으므로 총 거리에서 빼준다.

사고

swap 으로 자리를 바꿀 수 있는 원소들은 어떤 배열로든 만들 수 있다. 따라서 연결되어 있는 인덱스들로 그룹을 나누고, 특정 그룹의 원소들을 source 와 target 을 살펴서 source[i] == target[i] 여부를 확인할 수 있다. e.g. allowedSwaps =[[1, 2],[0, 2]] 라면 0, 1, 2 인덱스는 한 묶음이다. 이에 대해 target[i] (i = 0, 1, 2) == source[0] or source[1] or source[2] 라면 자리를 바꿔서 같은 원소를 놓을 수 있다는 뜻이므로 거리가 0이다. union-find 나 bfs 로 접근가능하다.

 

from collections import deque
from collections import defaultdict
class Solution:
    def minimumHammingDistance(self, source: list[int], target: list[int], allowedSwaps: list[list[int]]) -> int:
        graph = [[] for _ in range(len(source))]
        visited = set()
        dist = 0 #총 거리

        for a, b in allowedSwaps:
            graph[a].append(b)
            graph[b].append(a)

        for i in range(len(source)):
            # q 로 도는 bfs 한번에 한 그룹이다. while 문이 끝나면 lst 와 subset 에 각각 그룹의 index 값과 그룹에 특정 원소가 몇개인지 담긴다.
            q = deque([i])
            subset = defaultdict(int)
            lst = []
            while q:
                id = q.popleft()
                if id in visited:
                    continue
                subset[source[id]] += 1
                lst.append(id)
                visited.add(id)
                for nxt_id in graph[id]:
                    if nxt_id not in visited:
                        q.append(nxt_id)
            subtract = 0
            for ele in lst:
                if subset[target[ele]] > 0:
                    subtract += 1
                    subset[target[ele]] -= 1
            dist += len(lst) - subtract
        return dist

submission