프로그래머스 네트워크

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

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

 

풀이 : BFS를 이용해 지점을 잇는 경로를 탐색

① 지점을 잇는 경로를 탐색한다.

② ①에서 탐색되지 않은 지점를 시작으로 재탐색한다.

* computer[i][i] 가 1이므로, 어느 지점과 연결되지 않으면 자기자신하고만 연결되는 경로 (네트워크) 1개가 세어진다.

2021.09.19 - [알고리즘/알고리즘] - 너비 우선 탐색 Breath-first Search BFS

너비 우선 탐색 Breath-first Search BFS

 

구현 JAVA

import java.util.*;

class Solution {
       public int solution(int n, int[][] computers) {
    	
    	boolean[] visited = new boolean[n];
    	int network = 0;

    	for(int i = 0; i<n; i++) {
    		if(visited[i]) {
    			continue;
    		}else {
    			bfs(i, computers, visited);
    			network++;
    		}
    	}
        return network;
    }
	
    public void bfs(int now, int[][] computers, boolean[] visited) {
 
    	Queue<Integer> q = new LinkedList<Integer>(); //경로를 저장할 queue
    	visited[now] = true;// 현재 방문 여부를 지정
    	q.add(now); //현재 위치를 경로에 저장
    	
    	while(q.size()>0) { 
    		//현재 위치를 경로에서 추출
    		now = q.poll();
    		//현재 위치와 이어져 있는 지점을 탐색
    		for(int i = 0; i<computers.length; i++) {
    			//방문한 지점이 방문한 적이 없다면 지점을 저장
    			if(!visited[i] && computers[now][i] == 1) {
    				visited[i] = true;
    				q.add(i);
    			}
    		}
    	}
    }
}