네트워크

작성일: 2024-10-18

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제에 대한 내용

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한 조건

  • 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
  • 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
  • i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
  • computer[i][i]는 항상 1입니다.

입출력 예

n computers return
3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2
3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다. alt text

예제 #2
아래와 같이 1개의 네트워크가 있습니다. alt text

접근 방식

  1. dfs로 출발 노드에서 출발한다.
  2. 이어진 노드를 방문한다.
  3. 1,2를 반복하면서 방문하지 않았던 노드에 대해서는 방문시 네트워크의 개수를 +1 한다.

결과

소스 코드 

class Solution {

    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]){
                dfs(n, computers, i, visited);
                answer++;
            }
        }

        return answer;
    }

    private void dfs(int n, int[][] computers, int idx, boolean visited[]) {

        visited[idx] = true;

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

    }
}

solution 함수

  1. n개의 컴퓨터 수만큼 for문을 돈다.
  2. 만약 i번째 컴퓨터를 방문하지 않았다면, 그 컴퓨터에서 dfs를 시작한다.
  3. dfs를 마치고 나오면 answer를 +1 한다. (방문하지 않았었기에 네트워크 수 +1)

dfs 함수

  1. 현재 컴퓨터를 방문처리한다.
  2. 현재 컴퓨터의 노드를 확인한다.
  3. 만약 현재 노드와 연결되어 있고, 내가 해당 노드를 방문한 적이 없다면, dfs를 호출해서 타고 들어간다.

결과 이미지

alt text

다른 접근 방식

BFS 

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        Queue<Integer> que = new LinkedList<>();
        boolean visited[] = new boolean[n];
        for(int i=0; i<n; i++){
            if(!visited[i]){
                bfs(n, computers, que, i, visited);
                answer++;
            }
        }

        return answer;
    }

    private void bfs(int n, int[][] computers, Queue<Integer> que, int idx, boolean visited[]){

        que.offer(idx);

        while(!que.isEmpty()){
            int start = que.poll();
            visited[start] = true;
            for (int i=0; i<n; i++){
                if (computers[start][i] == 1 && !visited[i]) que.offer(i);
            }
        }

    }
}

solution 함수

  1. Queue를 이용해서 인전한 노드의 주변 노드를 탐색한다.
  2. 먼저, 0번째 컴퓨터의 노드부터 탐색을 시작한다.

bfs 함수

  1. 먼저 탐색할 컴퓨터의 인덱스를 que에 넣는다.
  2. 인접한 노드를 모두 탐색한다. (que가 빌 때까지)
  3. 먼저 큐에서 컴퓨터를 꺼낸다.
  4. 해당 컴퓨터를 방문처리 한다.
  5. 해당 컴퓨터의 관련 노드를 탐색한다.
  6. 만약 해당 노드와 연결되어 있고, 방문한 적 없는 컴퓨터의 노드라면 큐에 넣는다.
  7. 위의 로직을 반복하며, 인접한 노드를 모두 탐색한다.

알게 된 점

없음