Bfs

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 로 접근가능하다. ...