[LeetCode] 547. Number of Provinces, Medium

1. 문제

• 2차원 배열의 좌표로 각 도시의 연결 정보가 주어질 때, 직접 혹은 간접으로 연결된 그룹을 한 개로 보고 존재하는 지방 도시의 개수를 구해라.

2. 해결

function findCircleNum(isConnected: number[][]): number {

    let count = 0;

    function DFS(y: number) {

        for(let i =0; i < isConnected.length; i++) {

            if(isConnected[y][i] === 1) {
                isConnected[y][i] = 0;
                isConnected[i][y] = 0;
                DFS(i);
            }
        }
    }

    for(let i = 0; i < isConnected.length; i++) {
        for(let j =0; j < isConnected.length; j++) {

            if(isConnected[i][j] === 1) {
                isConnected[i][j] = 0;
                isConnected[j][i] = 0;

                DFS(j);
                count++;
            }
        }
    }

    return count;
};

• 좌표를 탐색하면서, 연결 정보가 있으면 타고, 타고 올라가서 연결 정보를 모두 지운다.
• 이 과정이 끊나면 한 그룹의 탐색이 끝난 것이므로 count 증가.
• 뭔가 2중 for문이라 리팩토링할 수 있을 거 같은데..