[코딩테스트] Java 네트워크

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

연결되어 있는 노드를 DFS로 이동하면서 트리의 갯수를 찾는 문제입니다.

union-find로도 문제를 풀 수 있겠지만 DFS를 통해 문제를 해결했습니다. 

소스코드

import java.util.ArrayList;

class Solution {
    boolean[] visited;
    int answer = 0;
    
    public void dfs(int n, int start, int[][] computers) {
        visited[start] = true;
        for(int i = 0; i < n; i++) {
            if (i == start) continue;
            if (!visited[i] && computers[start][i] == 1) {
                dfs(n, i, computers);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(n, i, computers);
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

public void dfs(int n, int start, int[][] computers) {
    visited[start] = true; // 현재 컴퓨터를 방문 처리
    for(int i = 0; i < n; i++) { // 모든 컴퓨터를 탐색
        if (i == start) continue; // 자기 자신과의 연결은 무시
        if (!visited[i] && computers[start][i] == 1) { // 방문하지 않았고 연결된 경우
            dfs(n, i, computers); // 재귀 호출로 탐색
        }
    }
}

• visited[start] = true;
  현재 컴퓨터는 방문 처리합니다
• for문
  자기 자신과의 연결은 무시한 후 방문하지 않았고 연결된 경우 재귀 호출로 탐색합니다.

public int solution(int n, int[][] computers) {
    visited = new boolean[n]; // 방문 여부를 초기화
    for(int i = 0; i < n; i++) { // 모든 컴퓨터를 순회
        if (!visited[i]) { // 방문하지 않은 컴퓨터를 발견하면
            dfs(n, i, computers); // 해당 컴퓨터에서 연결된 네트워크 탐색
            answer++; // 네트워크 개수 증가
        }
    }
    return answer;
}

• visited 배열을 초기화 한 후 방문하지 않은 네트워크 중 연결된 네트워크의 갯수를 for문을 통해 순회합니다.