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

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

문제는 위와 같으며, dfs를 통해 문제를 해결하였습니다.

 

모든 컴퓨터가 연결되어 있는지 한번씩은 확인을 해야하므로 이를 확인할 수 있는 boolean 타입의 배열을 생성합니다. 이 배열을 순서대로 반복하면서 해당 위치의 컴퓨터를 아직 방문하지 않은 경우 dfs를 통해 연결된 모든 컴퓨터를 방문처리합니다. 그러고 나면 하나의 네트워크를 확인한 것이므로 answer를 증가시킵니다.

 

dfs 메소드를 살펴보면 먼저 해당 컴퓨터를 방문한 것으로 처리하고, 이 컴퓨터에 대한 연결 정보를 모두 확인하면서 연결이 되어있지만 아직 방문하지 않은 다음 컴퓨터를 기준으로 하여 다시 dfs 메소드를 수행하게 됩니다.

 

JAVA 코드는 다음과 같습니다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;

        boolean[] visited = new boolean[n]; // 연결된 컴퓨터를 확인했는지 체크
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {  // 아직 해당 컴퓨터를 확인하지 않은 경우
                dfs(computers, visited, i);  // 기준 컴퓨터와 연결된 컴퓨터를 모두 확인
                answer++;
            }
        }

        return answer;
    }

    private static void dfs(int[][] computers, boolean[] visited, int start) {
        visited[start] = true;  // 기준 컴퓨터를 확인한 것으로 처리하고
        for (int i = 0; i < computers[start].length; i++) {
            if (computers[start][i] == 1 && !visited[i]) {  // 기준 컴퓨터와 연결되어 있지만 아직 확인하지 않은 경우
                dfs(computers, visited, i);  // 다시 다음 컴퓨터를 기준으로 연결된 컴퓨터 모두 확인
            }
        }
    }
}