[프로그래머스, 자바] 네트워크 - 그래프 BFS

프로그래머스 3단계 네트워크 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/43162?language=java

문제설명

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

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

제한사항

컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.

i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다. computers[i][j]는 항상 1입니다.

입출력 예

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

자바코드

            
package Q43162;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

public class Solution {
    /*
	 	문제 : 네크워크
	 	url : https://programmers.co.kr/learn/courses/30/lessons/43162
	 	재풀이 : O
	*/

    public int solution(int n, int[][] computers) {
        int answer = 0;
        Queue queue = new ConcurrentLinkedQueue();
        List list = new ArrayList();
        boolean[] visited = new boolean[computers.length];

        for (int i = 0; i < computers.length; i++)
            list.add(new Node(i));

        for (int i = 0; i < computers.length; i++)
            for (int j = 0; j < computers[0].length; j++)
                if(computers[i][j] == 1 && i != j)
                    list.get(i).addAdjacent(list.get(j));

        for (int i = 0; i < list.size(); i++) {
            if(!visited[i]) {
                queue.add(list.get(i));
                visited[i] = true;
                answer++;
            }

            while(!queue.isEmpty()) {
                Node pop = queue.poll();
                List nodes = pop.adjacent;
                for (Node node : nodes) {
                    if(!visited[node.data]) {
                        visited[node.data] = true;
                        queue.add(node);
                    }
                }
            }
        }

        return answer;
    }

    public class Node {
        private int data;
        private List adjacent = new ArrayList();

        public Node(int data) {
            this.data = data;
        }

        public void addAdjacent(Node node) {
            adjacent.add(node);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] computers = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        System.out.println(solution.solution(3, computers));

        int[][] computers2 = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
        System.out.println(solution.solution(3, computers2));
    }
}

문제설명

이 문제는 너비탐색 알고리즘을 이용해서 풀었다. 이 문제에서 가장 어려웠던 점을 너비탐색을 구현하는 것이 아닌, 각각의 네트워크를 표현하는 부분이었다.

네트워크 표현을 위해 각각의 컴퓨터를 하나의 노드로 설정하여, 그래프의 형태로 구현을 했다. 그리고 각각의 노드는 인접한 노드에 대한 리스트를 가지게 했다.

그래서 하나의 노드를 기준으로 네트워크를 찾을 때, 모든 인접한 노드를 방문하게 하여 카운트 하였다. 그리고 이전에 방문했던 노드에 대해 중복적으로 방문하지 않기 위해 

bool 배열을 이용해 중복방문을 하지 않게 체크를 하였다. 그리고 BFS 구현을 위한 큐를 사용했다. 이 문제에서 중간 중간 출력결과를 확인하기 위해 toString() 메소드를 

오버라이딩했는데 그 결과 인접한 노드가 서로를 참조하고 있기 때문에 스택오버플로우 오류가 발생했다. 이 부분은 제어가 필요했다.

이 문제에서 핵심이 되는 부분은 처음에 각각의 인접 노드에 대해 셋팅했을 때, 인접 노드를 추가하는 과정에서 인접 노드를 새로 생성하여 추가하는 것이 아닌, 기존에 생성했던 

인접 노드를 추가해야 한다. 그렇지 않으면, 인접 노드에 인접노드를 확인할 수 없다. 그래서 초기에 셋팅을 위한 반복문이 두번 필요했다. 

(첫번째 반복문은 인접 노드를 갖지 않는 노드를 생성하기 위한 반복문, 두번째 반복문은 빈 노드에 인접 노드를 추가하는 반복문)

2월 중에 프로그래머스 단계별 알고리즘을 모두 푸는 것이 목표이다!