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

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

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

우선 DFS로 풀었으며 풀면서 내가 크게 착각한것이 있다.

 

DFS로 풀 때 항상 2차원 배열을 만들고 두 그래프가 대칭이라고 생각했었고, 주어진 케이스에서도 대칭인줄 알았으나

 

그렇게 생각하고 풀게 되니 테스트 케이스가 2개만 맞았다. 

 

1->2 (0) 2->1 (X 일 수도 있음)

 

이 사실을 깨닫고 풀이를 고치니 맞았음.

 

 

public class Network {
    static int [] visited = new int[201];

    public static void DFS(int startx, int n, int [][]computers) {
        visited[startx] = 1;
        for(int i = 0 ; i < n; i++ ) {
            if(visited[i] == 0 && computers[startx][i] == 1) {
                DFS(i, n, computers);
            }
        }
    }
    public static int solution(int n, int[][] computers) {
        int answer = 0;
        for(int i = 0; i<n; i++) {
                //computers[i][j] 는 항상 1이기 떄문에 0부터 시작해도 된다.
                if(visited[i]== 0) {
                    DFS(i,n, computers);
                    answer ++;
                }           
        }
        return answer;
    }

    public static void main(String[] args) {
        int [][] test = {{1,1,0}, {1,1,1}, {0,0,1}};
        int ans = solution(3, test);
    }
}