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

이 문제는 백준에서도 봤던 문제같다.

풀이 생각

(0:20)

• 하나의 노드로부터 dfs, bfs등을 통해, 이 노드와 같은 네트워크에 속해 있는 노드들을 파악할 수 있다.
  • 이 때 visit을 체크한다
• visit되지 않은 노드로부터 또다시 탐색을 한다.
  • 시작 할 때에만 network의 수를 늘려주도록 한다.
• 어차피 모든 노드를 한 번씩 방문하는게 된다.
• 그럼에도 20분 걸린 것은, 주어지는 데이터의 구조를 제대로 보지 않았다;;; 💥💥 엄청난 실수다. 알 것 같은 문제더라도 문제를 꼼꼼히 읽고 한 번에 파악하는 것이 중요하다. 특히나 주어지는 데이터의 구조를 파악하지 못하면 문제를 풀 때 갑자기 당황할 수가 있다 💥💥

import java.util.*;
class Solution {
    public boolean[][] dup_check = new boolean[200][200];
    public List<Integer>[] info = new List[200];
    public boolean[] visit = new boolean[200];
    public int cnt=0;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        int v1=0,v2=0;
        // init
        for(int i=0;i<n;i++)
            info[i]= new LinkedList<>();
        // bidirectional setting 
        for(int i=0;i<computers.length;i++){
            for(int j=0;j<computers[i].length;j++){
                if(i==j) continue; 
                if(computers[i][j]==0)continue;
                if(dup_check[i][j])continue;
                // 중복이 존재할 수 있다. 시간을 줄이고 싶다면 여기서 줄여도 좋음.
								// 물론 dup_check를 하지 않아도, 어차피 vist된 것으로 처리되어있기에, 다시 방문하지는 않는다.  
                info[i].add(j);
                info[j].add(i);
                dup_check[i][j]=true;
                dup_check[j][i]=true;
            }
            
        }
        // iterate all node
        for(int i=0;i<n;i++){
            if(visit[i]) continue;
            bfs(i);
        }
        answer= cnt;
    
        return answer;
    }
    public void bfs(int i){
        cnt++; // increment the number of networks 
        Queue<Integer> q = new LinkedList<>();
        visit[i]=true;
        q.add(i);
        int cur=0;
        while(q.isEmpty()==false){
            cur= q.poll();
            for(Integer next:info[cur]){
                if(visit[next])continue;
                q.add(next);
                visit[next]=true; 
            }
        }
    }
}

테스트 1 〉	통과 (0.27ms, 76.7MB)
테스트 2 〉	통과 (0.24ms, 77.1MB)
테스트 3 〉	통과 (0.34ms, 73.4MB)
테스트 4 〉	통과 (0.36ms, 82.3MB)
테스트 5 〉	통과 (0.25ms, 80.7MB)
테스트 6 〉	통과 (0.64ms, 75.7MB)
테스트 7 〉	통과 (0.25ms, 77.4MB)
테스트 8 〉	통과 (0.42ms, 76.2MB)
테스트 9 〉	통과 (0.36ms, 87MB)
테스트 10 〉	통과 (0.36ms, 75.8MB)
테스트 11 〉	통과 (1.53ms, 85.8MB)
테스트 12 〉	통과 (1.01ms, 72.1MB)
테스트 13 〉	통과 (0.65ms, 78.1MB)

다른 사람 풀이

• 이 문제는 주어진 데이터를 가지고 따로 graph 정보를 만들지 않아도 되는 문제였다.
• 왜냐하면 이미 matrix정보가 주어진 것이기 때문이다....그저 computers[i]를 읽으면, i의 인접 노드들을 1인 값에서 확인이 가능했다.. 어차피 visit을 사용하면 되기에 comptuers[i][i]를 중복 방문할 일도 없다. (.💥문제를 정말 제대로 읽지 않은 문제였다 )

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