LeetCode DFS문제: 1202. Smallest String With Swaps(Sorting, DFS, 자바스크립트 이중배열)

https://leetcode.com/problems/smallest-string-with-swaps/

Smallest String With Swaps - LeetCode

 

 

정렬과 DFS가 같이 혼합된 문제이다.

문제의 핵심은 pairs에서 swap 할 수 있는 모든 인덱스들을 묶어서 swap 하는 데에 있다.

 

만약 swap 할 수 있는 인덱스가 (1,2) (2,3) 두 가지라면 결국 (1,2,3)끼리는 어느 위치로든 swap 할 수 있는 것이다.

 

그래서 풀이 단계를 이렇게 정리할 수 있다.

① pairs를 참고하여 swap 할 수 있는 연결된 값들을 정리한다. (이때 [0]번과 [1]번을 각각 저장해줌)

② 문자 길이인 n만큼 반복문을 돌려서 각 알파벳이 swap 할 수 있는(①에서 저장한 연결된 정보를) DFS 해준다.

③ DFS함수에서는 방문 체크를 해주고 paths에 swap 할 수 있는 연결된 인덱스를 저장해준다.

④ 현재 알파벳과 연결된 swap정보들이 다 모였다면 1. swap 할 수 있는 인덱스와 2. 그 인덱스들에 해당하는 알파벳들만 꺼내서 두 가지를 정렬한다.

⑤ 원래 문자열에다가 ④에서 정렬해준 인덱스 위치에 정렬한 알파벳들을 대체해서 넣어주면 사전 순으로 앞 인덱스부터 넣어줄 수 있다.

 

 

 

<Python>

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        def dfs(curr):
            if not visited[curr]:
                visited[curr] = True
                # 상위 스코프 paths에 추가. 아래에서 dfs돌리면 각 depth로 들어가게돼서 바깥에서 관리해야함
                paths.append(curr)
                for nexts in link[curr]:
                    dfs(nexts)
            return
        
        n = len(s)
        link = [[] for _ in range(n)]  # 인덱스를 키로해서 pairs에서 짝이되는 모든 값들 저장
        lists = list(s)
        visited = [False for _ in range(n)]
        for p in pairs:
            # 0번이랑 1번 중 어디가 다른 노드랑 연결될 지 모르기때문에 둘 다 저장
            link[p[0]].append(p[1])
            link[p[1]].append(p[0])
        
        for i in range(n):
            paths = []  # i랑 연결된 swap 할수있는 모든 인덱스 관리할곳
            dfs(i)
            
            chars = [lists[p] for p in paths]
            
            paths.sort()
            chars.sort()
            for k in range(len(paths)):
                lists[paths[k]] = chars[k]  # 정렬한 인덱스와 문자열을 다시 끼워넣음
            
        
        return ''.join(lists)

 

<JavaScript>

/**
 * @param {string} s
 * @param {number[][]} pairs
 * @return {string}
 */
var smallestStringWithSwaps = function(s, pairs) {
    const dfs =(curr)=>{
        if(!visited[curr]){
            visited[curr] = true;
            paths.push(curr);
            
            for(const next of linked[curr]){
                dfs(next);
            }
        }
        return;
    }
    
    const n = s.length;
    const linked = Array.from(Array(n), () => []);
    const paths = [];
    const visited = new Array(n).fill(false);
    const list = s.split('');
    
    for(const p of pairs){
        linked[p[0]].push(p[1]);
        linked[p[1]].push(p[0]);
    }
    for(let i=0; i<n; i++){
        paths.splice(0);  // i마다 새로운 paths를 가져야 하기때문에 매번 초기화해줘야함
        dfs(i);
        
        const chars = [];  // paths에서 모은 인덱스들에서 거기에 해당하는 문자만 가져올거임
        for(const p of paths){
            chars.push(list[p]);
        }
        chars.sort();
        paths.sort((a,b)=>a-b);
        for(let x=0; x<paths.length; x++){
            list[paths[x]] = chars[x];  // 앞 인덱스부터 정렬된 알파벳 대체하기
        }
    }
    
    return list.join('');
};