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

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

프로그래머스

 

사용 알고리즘

• 그래프 탐색
• BFS

풀이

 

import java.util.*;
class Solution {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean [] visited;
    static int answer = 0;
    public int solution(int n, int[][] computers) {
        
        for(int i = 0; i < n; i++){
            graph.add(new ArrayList<>());
        }
        visited = new boolean[n];
        
        for(int i = 0; i < computers.length; i++) {
            for(int j = i + 1; j < computers[i].length; j++) {
                if (computers[i][j] == 1) { // 서로 이어져있는 경우 그래프에 추가
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            if (!visited[i]) {
                bfs(i);
                answer++;
            }
        }
        
        return answer;
    }
    
    public void bfs(int start) {
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
      
        queue.add(start);
        while(!queue.isEmpty()) {
            int node = queue.poll();
            for(int next : graph.get(node)) {
                if (visited[next]) continue;
                visited[next] = true;
                queue.add(next);
            }
        }
    }
    
}

 

회고

 

그래프 문제들을 쭉 풀었더니 쉽게 해결이 가능했다. 

 

그런데, 처음에 bfs를 돌릴 때 0부터 n-1 까지가 아닌 1부터 n까지 돌렸더니 기댓값 + 1로 나오길래 하드코딩해서 결과에서 -1을 빼서 리턴해줬더니 통과했다..

 

너무 주먹구구식으로 통과한 것 같아서 문제를 잘 살펴보니

• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.

라는 조건이 있었다. 0부터 n-1까지 bfs를 다시 돌려줬더니, 하드코딩 하지 않아도 정상적으로 통과가 되었다.

정확성 테스트

테스트 1 〉	통과 (0.31ms, 77MB)
테스트 2 〉	통과 (0.20ms, 70.4MB)
테스트 3 〉	통과 (0.29ms, 71.9MB)
테스트 4 〉	통과 (0.23ms, 67.3MB)
테스트 5 〉	통과 (0.17ms, 70.2MB)
테스트 6 〉	통과 (0.57ms, 83.2MB)
테스트 7 〉	통과 (0.42ms, 70.3MB)
테스트 8 〉	통과 (0.47ms, 69.3MB)
테스트 9 〉	통과 (0.37ms, 65.5MB)
테스트 10 〉	통과 (0.30ms, 79.9MB)
테스트 11 〉	통과 (1.30ms, 90.2MB)
테스트 12 〉	통과 (0.84ms, 73.8MB)
테스트 13 〉	통과 (4.97ms, 75.6MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0