[프로그래머스] 43162번 : 네트워크

코드

public class PRO_43162 {
    public static int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(computers, visited, i);
                ++answer;
            }
        }
        return answer;
    }

    public static void dfs(int[][] computers, boolean[] visited, int start) {
        visited[start] = true;

        for (int i = 0; i < computers.length; i++) {
            if (computers[start][i] == 1 && !visited[i])
                dfs(computers, visited, i);
        }
    }


    public static void main(String[] args) {
        int n = 3;
        int[][] computers = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};

        System.out.println(solution(n, computers));
    }
}

풀이 및 느낀점

깊이우선탐색(dfs)을 사용하여 문제에 접근했다. boolean형 방문배열을 만들었고, 컴퓨터의 길이만큼 반복하면서 각 컴퓨터를 dfs메소드에 접근시켰다.

dfs 메소드 내에서는 현재 컴퓨터의 방문을 true로 바꿔준다. 컴퓨터 배열의 길이만큼 반복하면서 시작점과 연결된 컴퓨터 배열 값이 1이고 방문하지 않았다면, dfs 메소드를 재귀호출한다.

dfs메소드를 돌고 빠져나오면 answer의 값을 1 증가시켜준다.

참고자료