[프로그래머스 | JAVA ] LV. 3 : 네트워크

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] :   LEVEL 3 

프로그래머스 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

---

● 풀이 방법

해당문제는 여러대의 컴퓨터가 나열되어 있는 그림에서 네트워크 연결도를 보고 총 몇개의 네트워크 그룹이 있는지 구하는 문제이다.

이 문제는 BFS로 풀어야 겠다고 판단하였으며, 각 컴퓨터를 방문했지에 대한 정보를 가질 수 있는 배열과,

해당 컴퓨터로부터 네트워크 연결 정보를 임시로 저장하여 다음 컴퓨터에 연결된 네트워크 상태 정보를 확인할  수 있게 Queue 를 사용하였다.

 

문제의 예제인 아래를 기반으로 설명을 하자면

우선 첫번째 computer[0]을 확인하여 연결되어 있는 노드를 확인한다. 

첫번째 노드와 두번째 노드가 연결되어 있다는 뜻의 숫자 1이 있다.

이를 통해 확인하고자 하는 노드값인 1을 queue에 넣은 후,

자신과 연결되어 있는 노드의 번호가 있는지 확인함과 동시에 확인하고자 하는 노드 값이었던 1을 poll한다. 이후 연결되어 있는 노드가 있었다면 해당 노드에 관하여 방문한 적이 없는지를 확인 후, 방문한 적이 없는 노드(computer)라면 해당 값도 queue에 넣어버린다. 이를 while문으로 노드를 계속 반복적으로 체크하며 queue에 넣거나 빼는 작업을 통해 연결되어 있는 노드(computer)들의 방문이력을 남겨놓는다. 

 

---

● 소스 코드

import java.util.*;

class Solution {
	Queue<Integer> que = new LinkedList<>();
    boolean[] visit;

	public int solution(int n, int[][] computers) {
        int answer = 0;
        visit = new boolean[n];

        for(int i=0; i<n; i++) {
            if(visit[i] == false) {
                BFS(i, computers, n);
                answer++;
            }
        }
        return answer;
    }

	public void BFS(int i, int computers[][], int n) {
		que.offer(i);
		visit[i] = true;	

		while( !que.isEmpty() ) {
			int value = que.poll();

			for(int j=0; j<n; j++) {
				if(visit[j] == false && computers[value][j] == 1) {
					visit[j] = true;
					que.offer(j);
				}
			}

		}
	}
}

 

---

● 결과