[Programmers] 네트워크

문제

• 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162
• 사용언어: Java
• IDE: IntelliJ
• 알고리즘: 깊이 우선 탐색(DFS)

풀이

public class NetworkSolution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfsConnectionOfComputers(computers, i, visited);
                answer++;
            }
        }
        return answer;
    }

    private boolean[] dfsConnectionOfComputers(int[][] statusOfConnection, int index, boolean[] visited) {
        visited[index] = true;

        for (int next = 0; next < statusOfConnection.length; next++) {
            if (needsToVisit(statusOfConnection, index, visited, next)) {
                visited = dfsConnectionOfComputers(statusOfConnection, next, visited);
            }
        }
        return visited;
    }

    private boolean needsToVisit(int[][] connectionStatus, int index, boolean[] visited, int next) {
        return index != next && connectionStatus[index][next] == 1 && visited[next] == false;
    }
}

테스트코드

import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

import static org.junit.jupiter.api.Assertions.*;

class NetworkSolutionTest {
    @ParameterizedTest(name = "입출력 예시로 테스트{0}")
    @MethodSource("provideTestCases")
    void test(int numberOfComputers, int[][] statusOfConnections, int result) {
        NetworkSolution network = new NetworkSolution();
        assertEquals(result, network.solution(numberOfComputers, statusOfConnections));
    }

    private static Stream<Arguments> provideTestCases() {
        return Stream.of(
                Arguments.of(3, new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}, 2),
                Arguments.of(3, new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}}, 1)
        );
    }
}