프로그래머스 - 네트워크

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

 

문제 출처

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

 

[문제 설명]

컴퓨터끼리 연결되어 있으면 하나의 네트워크로 본다. 총 네트워크의 개수는?

[처음 생각한 접근 방법]

BFS 문제 답게 이어져 있는 컴퓨터를 하나 방문하고, 그 컴퓨터와 이어져 있는 모든 컴퓨터들을 방문한다.

이어져 있는 모든 컴퓨터들을 방문하면 그게 하나의 네트워크가 되므로, 네트워크를 1개 추가해준다.

그리고 다음 컴퓨터로 넘어가되, 다음 컴퓨터가 이전 컴퓨터에 네트워크의 속한 컴퓨터인지 확인한다.

그림을 예로 들었을 때 위와 같은 네트워크가 있다고 보자.

우선 A부터 순서대로 검색하기로 하자, A의 연결 관계를 본다.

A는 B와 연결 되어 있다. 그렇다면 B는 방문한 걸로 치고, 이제 B가 연결된 요소들을 찾는다.

B는 D와 연결 되어 있다. 그렇다면 D도 방문한 걸로 치고, 이제 D와 연결된 요소들을 찾는다.

D는 C와 연결 되어 있다. D도 방문 처리를 한 후, 이제 C와 연결 된 요소들을 찾는다.

C는 아무하고도 연락되어 있지 않다. 이제 C를 방문 처리하고 A부터 시작한 모든 네트워크가 끝났으므로 네트워크의 개수를 1추가한다.

이제 A로부터 시작한 모든 네트워크가 끝났으니 B에서 위에 과정을 반복한다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    //boolean형 배열을 통한 코드.
    public int solution(int n, int[][] computers) {
        boolean[] visitedIndex = new boolean[n];        //컴퓨터들의 방문 여부를 체크하기 위한 boolean 배열.
        Queue<int[]> queue = new LinkedList<>();        //BFS 구현을 위해 만든 큐.
        int answer = 0;                                    //네트워크의 개수.

        for (int i = 0; i < computers.length; i++) {    //네트워크의 시작 기준을 queue에 넣어줄 반복문.
            if (visitedIndex[i] == true) {                //방문한 컴퓨터면 다음 컴퓨터로 넘어간다.
                continue;
            }

            queue.offer(computers[i]);                    //네트워크의 시작점이 될 컴퓨터를 queue에 넣어줌.
            visitedIndex[i] = true;                        //시작점은 이제 방문했으므로 방문 여부 true.
            while (!queue.isEmpty()) {                    //시작점과 연결된 모든 컴퓨터의 검색이 끝날 때까지 계속.
                int[] computer = queue.poll();            //시작점 컴퓨터를 뽑아줌.

                for (int j = 0; j < computer.length; j++) {        //연결된 컴퓨터들을 모두 queue에 넣어줌.
                    if (j == i || visitedIndex[j] == true) continue;
                    if (computer[j] == 1) {
                        visitedIndex[j] = true;
                        queue.offer(computers[j]);
                    }
                }
            }
            answer++;                                    //시작점과 이어진 모든 컴퓨터의 검색이 끝났으므로, 네트워크 개수 증가.
        }

        return answer;
    }
}

import java.util.*;

class Solution {
    //set을 이용한 코드.
    public int solution(int n, int[][] computers) throws InterruptedException {
        Set<Integer> visitedIndex = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        int answer = 0;

        for (int i = 0; i < computers.length; i++) {
            if (visitedIndex.add(i) == false) {
                continue;
            }

            queue.offer(computers[i]);
            visitedIndex.add(i);
            while (!queue.isEmpty()) {
                int[] computer = queue.poll();

                for (int j = 0; j < computer.length; j++) {
                    if (j == i || visitedIndex.contains(j)) continue;
                    if (computer[j] == 1) {
                        visitedIndex.add(j);
                        queue.offer(computers[j]);
                    }
                }

            }
            answer++;
        }

        return answer;
    }
}

[리팩토링]

j를 이용한 for문에서 j는 i+1부터 시작해도 된다.(i번째에서 시작한 네트워크이기 때문에. i번째는 당연히 연결되어있음)****

또한, 이렇게 되면 i==j를 체크할 필요가 없다. 무조건 j는 i보다 크기 때문에.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    //boolean형 배열을 통한 코드.
    public int solution(int n, int[][] computers) {
        boolean[] visitedIndex = new boolean[n];
        Queue<int[]> queue = new LinkedList<>();
        int answer = 0;

        for (int i = 0; i < computers.length; i++) {
            if (visitedIndex[i])    continue;

            queue.offer(computers[i]);
            visitedIndex[i] = true;
            while (!queue.isEmpty()) {
                int[] computer = queue.poll();

                for (int j = i+1; j < computer.length; j++) {    //여기가 j+1로 바뀜.
                    if (visitedIndex[j]) continue;                //조건에 i == j 일 때 continue가 빠짐.
                    if (computer[j] == 1) {
                        visitedIndex[j] = true;
                        queue.offer(computers[j]);
                    }
                }
            }
            answer++;
        }

        return answer;
    }
}