이번에 풀어본 문제는
프로그래머스 네트워크 입니다.

📕 문제 링크

❗️코드

유니온 파인드

import java.util.*;
class Solution {
    static int [] parents;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        int rows = computers.length;
        int cols = computers[0].length;
        parents = new int[n];

        // 자기자신을 부모로 초기화
        for (int i = 0; i < n; i++) parents[i] = i;

        for (int i = 0; i < rows; i++) {
            for (int j = i + 1; j < cols; j++) {
                if (computers[i][j] > 0) {
                    if (getParents(j) != j) {
                        setParents(j, i);
                    }
                    else {
                        setParents(i, j);
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (parents[i] == i) answer++;
        }
        return answer;
    }
    static void setParents(int parent, int child) {
        int p = getParents(parent);
        int c = getParents(child);
        parents[c] = p;
    }
    static int getParents(int child) {
        return parents[child] == child ? child : getParents(parents[child]);
    }
}

DFS

class Solution {
    static boolean [] isVisited;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        int rows = computers.length;
        isVisited = new boolean[n];
        for (int i = 0; i < rows; i++) {
            if (!isVisited[i]) {
                answer++;
                dfs(i, n, computers);
            }
        }
        return answer;
    }
    static void dfs(int root, int n, int [][] computers) {
        isVisited[root] = true;
        for (int i = 0; i < n; i++) {
            if (computers[root][i] > 0 && !isVisited[i]) {
                dfs(i, n, computers);
            }
        }
    }
}

📝 풀이

2차원 배열의 값이 1이면 두 인덱스 값이 서로 연결되있다고 간주합니다.
서로 연결된 네트워크는 1개의 네트워크일 때, 주어진 입력값으로 총 몇 개의 네트워크가 존재하는지 출력하는 문제입니다.
처음에는 보자마자 유니온 파인드로 풀었습니다. 그런데, 생각보다 걸리는 테스트케이스가 몇개 있었는지 계속 몇몇 케이스에서 실패가 떴고, 여차저차 해결은 했지만 다른 방식으로 풀어보고 싶어서 DFS로 다시 풀어보았습니다.

📜 후기

큰 차이는 없지만, 뭔가 DFS 풀이가 더 깔끔한 것 같습니다..ㅎㅎ