Leetcode 547 직관적 풀이 - 2026년 6월 8일

출처: Dev.to

Q1) 547. 주의 개수

👉 LeetCode 문제 링크
처음에는 배열의 합이 1인 행(즉, 도시가 자기 자신과만 연결된 경우)을 세면 나머지 모든 도시가 자연스럽게 하나의 주가 될 것이라고 생각했습니다.
그 논리의 결함은: 서로 연결되지 않은 여러 개의 독립된 도시 군집이 존재할 수 있다는 점을 완전히 간과했다는 것입니다(예: 두 도시는 서로 연결돼 있지만, 다른 세 도시는 별도의 그룹을 형성하는 경우).
이를 해결하기 위해 메모장을 꺼내 그래프를 시각적으로 그려보니, 이것이 전형적인 그래프 탐색 문제이며 깊이 우선 탐색(DFS)에 딱 맞는다는 것을 깨달았습니다.
초안에서는 외부 헬퍼 함수(allVisit)를 사용해 visited 배열을 반복적으로 스캔하도록 구현했는데, 이는 불필요한 오버헤드를 발생시켰습니다. 0부터 n‑1까지 모든 도시를 한 번 순회하면서 방문하지 않은 도시를 만나면 DFS를 호출하도록 하면 주의 개수를 훨씬 효율적으로 셀 수 있습니다.

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length;
        int provinces = 0;
        boolean[] visited = new boolean[cities];

        // 각 도시를 순회합니다. 아직 방문되지 않았다면,
        // 새로운 주의 시작을 의미합니다.
        for (int i = 0; i < cities; i++) {
            if (!visited[i]) {
                dfs(i, visited, isConnected);
                provinces++; // 주 개수 증가
            }
        }

        return provinces;
    }

    private void dfs(int city, boolean[] visited, int[][] matrix) {
        visited[city] = true;

        // 인접한, 아직 방문하지 않은 모든 도시를 방문
        for (int i = 0; i < visited.length; i++) {
            if (matrix[city][i] == 1 && !visited[i]) {
                dfs(i, visited, matrix);
            }
        }
    }
}