프로그래머스 - 네트워크[Java]

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

프로그래머스

 

dfs를 이용해서 쉽게 해결할 수 있는 문제이다.

 

예시

n	computers	
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]

 

 

 

우선 방문했던 컴퓨터를 또 방문하면 안되므로 visit배열을 통해 각 컴퓨터의 방문 여부를 저장해준다.

public static boolean[] visit;

 

 

이제 dfs 코드가 필요하다.

 

start 변수 ==> 현재 컴퓨터의 위치

n ==> 전체 컴퓨터 갯수

 

public static void dfs(int start,int n){
        visit[start]=true;
        for(int i=0; i<n; i++){
            if(!visit[i] && computer[start][i]==1 && i!=start){
                dfs(i,n);
            }
        }
    }

dfs 함수가 실행되면 visit[start]를 true로 만들어서 재방문을 방지해야한다.

 

for문 내에서 현재 컴퓨터와 연결된 컴퓨터를 찾아야 한다.

 

현재 컴퓨터에서 다음으로 방문할 컴퓨터가 될 조건은 다음과 같다.

1. computer[현재 컴퓨터][다른컴퓨터] =1 (서로 연결이 되어 있다.)
2. visit[다른 컴퓨터] =  false (방문했던 컴퓨터면 안됨)
3. i != 현재 컴퓨터 (자기 자신을 다음으로 방문하면 안됨)

 

이제 dfs를 for문에서 실행해주면 된다.

for(int i=0; i<n; i++){
            if(!visit[i]){
                dfs(i,n);
                answer++;
            }
        }

 

각 네트워크에서 더이상 방문할 수 있는 컴퓨터가 없으면 answer++ 하게 되어 네트워크가 카운트 된다.

 

 

<정답 코드>

import java.util.*;

class Solution {
    public static int[][] computer;
    public static boolean[] visit;
    public static int answer;
    public int solution(int n, int[][] computers) {
        answer=0;
        computer= computers;
        visit=new boolean[n];
        
        for(int i=0; i<n; i++){
            if(!visit[i]){
                dfs(i,n);
                answer++;
            }
        }
        return answer;
    }
    
    public static void dfs(int start,int n){
        visit[start]=true;
        for(int i=0; i<n; i++){
            if(!visit[i] && computer[start][i]==1 && i!=start){
                dfs(i,n);
            }
        }
    }
}