[JAVA]프로그래머스 - 네트워크 (고득점Kit)

- 문제 내용

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

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

---

- 문제 접근 방법

DFS방식으로 하여 연결된 정점(컴퓨터)은 방문처리 하면서 answer 값을 증가시켰다.

1. 1번 정점을 시작으로 간선(네트워크)에 의해 직접 혹은 간접 적으로 연결된 모든 정점을 DFS 방식으로 연결된것을 확인하고 answer++을 한다.

2. 방문처리되지 않은 정점을 다시 시작정점으로 하여 1번 과정을 반복하면된다.

 

방문배열의 크기는 정점 방문을 체크하는거라서 n으로 함.

computers[][](간선 연결여부)의 크기는 n개의 정점에대해 자기자신을 포함한 n개의 연결여부를 적어야 해서 [n][n] 크기로 함.

 

이 문제는 백준의 바이러스 문제를 먼저 풀고나면 쉽게 풀 수 있을것 같다.

https://record-developer.tistory.com/7

[JAVA]BOJ(백준) - 바이러스 - 2606

 

---

- 풀이

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] check = new boolean[n]; //방문 배열
        
        for(int i=0; i<n; i++) { //0~n-1개의 정점을 돌면서 방문여부 확인하면서 방문안된 정점을 시작으로 간선의 연결을 확인한다.
        	if(!check[i]) {
        		answer++; // 방문안된 정점은 다른 네트워크 이므로 answer++을 해줌.
        		dfs(i,n,computers, check); // dfs 호출
        	}
        }
        return answer;
    }
    
    //시작정점을 기점으로 연결된 모든 정점을 방문처리한다.
    //이과정을 거치면 네트워크 한개가 나오는것.
    public void dfs(int v, int n, int[][] computers, boolean[] check) {
    	check[v]=true;
    	
    	for(int i=0; i<n; i++) {
    		if(computers[v][i]==1 && !check[i]) {
    			dfs(i,n,computers,check); //dfs에 i를 주는건 v정점과 연결된 정점에서 시작하려고.
    		}
    	}
    }
}

---

- 마치며

여기선 DFS로 풀었지만 이문제도 BFS로 푸는것도 가능하다고 생각한다.

그리고 백준의 2606번 바이러스 문제부터 꼭 풀어보길 바란다.