프로그래머스 Lv.3 : 네트워크 🅾️

[문제]

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.

예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고,

컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.

따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때,

네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

프로그래머스

 

[풀이]

이번에는 시간 소요가 궁금해서 시간을 정확히 재어보았다.

일단 코테를 시작한 시간은 23:15 (문제 읽기 전)

 

문제를 읽고,

BFS와 DFS 중 뭐가 더 효율적일지 생각해보았고 내 생각에는 둘다 가능할 것 같았다.

나누어지는 분기점이 중요한 사항인데,

인접한 노드를 먼저 방문하면서 한 그래프를 돌고 넘어가는거나 아래를 쭉 돌고 넘어가는거나 비슷할 거라고 생각했기 때문!

그래서 비교적 익숙하다고 생각하는(^^..) DFS로 먼저 시도!

---

DFS

23:38 코드를 첫 제출했다.

결과는 "실패"!

import java.util.*;

class Solution {
    static List<List<Integer>> listArr;
    static boolean[] chk;
    static int cnt=0;
    
    public static void dfs(int idx) {
        if(idx==listArr.size()) return;
        if(!chk[idx]) cnt++;
        
        for(int i:listArr.get(idx)) {
            if(chk[i]) return;
            chk[i]=true;
            dfs(i);
        }
        
        dfs(idx+1);
    }
    
    public int solution(int n, int[][] computers) {
        listArr=new ArrayList<>();
        chk=new boolean[n];
        
        for(int i=0;i<computers.length;i++) {
            int[] arr=computers[i];
            List<Integer> list=new ArrayList<>();
            for(int j=0;j<arr.length;j++) {
                if(i==j) continue;
                if(arr[j]==1) list.add(j);
            }
            listArr.add(list);
        }
        
        dfs(0);
        return cnt;
    }
}

 

반례를 떠올려보았고, 반례는 {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}} 이었다!

dfs(idx+1)이 문제가 되었던 것,,

설명하자면 1번 노드에서 2번 노드를 갔다가 2번 노드에서 3번 노드를 또 돌기 때문에 cnt가 1번 더 카운트 된 것이다.

 

그림을 그리며 다시 생각을 해보았고

00:00 한 번 더 제출!!

import java.util.*;

class Solution {
    static List<List<Integer>> listArr;
    static boolean[] chk;
    static int cnt=0;
    
    public static void dfs(int idx) {
        if(idx==listArr.size()) return;
        
        for(int i:listArr.get(idx)) {
            if(chk[i]) continue;
            chk[i]=true;
            dfs(i);
        }
    }
    
    public int solution(int n, int[][] computers) {
        listArr=new ArrayList<>();
        chk=new boolean[n];
        
        for(int i=0;i<computers.length;i++) {
            int[] arr=computers[i];
            List<Integer> list=new ArrayList<>();
            for(int j=0;j<arr.length;j++) {
                if(i==j) continue;
                if(arr[j]==1) list.add(j);
            }
            listArr.add(list);
        }
        
        for(int i=0;i<listArr.size();i++) {
            if(chk[i]) continue;
            cnt++;
            dfs(i);
        }
        return cnt;
    }
}

 

결과는 "성공"!!! 😜

반례를 생각해가며 코드를 작성하니 수월하게 다시 풀렸다!

DFS로 푸는데 45분 소요!

---

BFS

BFS로는 6분만에 풀었다.

이미 문제의 로직을 알고 있어서 그런가 수월하게 풀었다!

import java.util.*;

class Solution {
    static List<List<Integer>> listArr;
    static boolean[] chk;
    static int cnt=0;
    
    public static void bfs(int idx) {
        Queue<Integer> queue=new LinkedList<>();
        queue.add(idx);
        while(!queue.isEmpty()) {
            int node=queue.poll();
            for(int i:listArr.get(node)) {
                if(chk[i]) continue;
                queue.add(i);
                chk[i]=true;
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        listArr=new ArrayList<>();
        chk=new boolean[n];
        
        for(int i=0;i<computers.length;i++) {
            int[] arr=computers[i];
            List<Integer> list=new ArrayList<>();
            for(int j=0;j<arr.length;j++) {
                if(i==j) continue;
                if(arr[j]==1) list.add(j);
            }
            listArr.add(list);
        }
        
        for(int i=0;i<listArr.size();i++) {
            if(chk[i]) continue;
            cnt++;
            bfs(i);
        }
        return cnt;
    }
}

 

 

결과적으로 비슷한 효율성을 가지고 있기는 한데, DFS가 조금 더 좋은 것 같당.

물론 내가 BFS 코드를 효율적이지 않게 짰을 가능성도 존재하긴 함(알린이니까..=알고리즘 어린이)

어쨌든 오늘의 코테는 진짜 끄읏. 어서 자고 내일을 준비해야겠다.. 🤤 두근두근