LeetCode 1722 Minimize Hamming Distance After Swap Operations 파이썬 해설 풀이
LeetCode 1722 Minimize Hamming Distance After Swap Operations
접근
- 연결되어 있는 인덱스 정보를 담을 그래프 graph, 방문 여부 visited 를 초기화한다.
- iteration 돌면서 각 i 가 아직 방문 안했다면 bfs로 연결된 인덱스를 모두 찾는다.
- 연결된 인덱스를 lst 에 담고 subset 에는 해당하는 인덱스의 source 값을 담는다.
- bfs 가 끝나면 lst 의 모든 원소에 대해 target[i] 가 subset 에 있는지 찾는다.
- 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
