[BFS] 네트워크 - Java

문제 바로가기

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

 

아주 간단한 BFS 문제입니다.

프로그래머스 구경하다가.. 문제가 너무 쉬워보일길래 한 번 풀어보았습니다.

IDE 안쓰고 코드짜는 것도 나름 재밌네요.

 

import java.util.*;

class Solution {
    public boolean[] visited;
    public List<Integer>[] graph;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        Arrays.fill(visited, false);
        graph = new List[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (computers[i][j] != 1) continue;
                
                graph[i].add(j);
                graph[j].add(i);
            }
        }
        
        for (int i = 0; i < n; i++) {
            System.out.println(graph[i].toString());
        }
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                answer++;
                bfs(i);
            }
        }
        
        return answer;
    }
    
    public void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            
            for (int i = 0; i < graph[cur].size(); i++) {
                int next = graph[cur].get(i);
                
                if (visited[next]) continue;
                visited[next] = true;
                q.offer(next);
            }
        }   
    }
}

 

입사하기 전에는 for 나 if 뒤에 띄어쓰기를 절대 안했는데 이제 안하면 찝찝합니다.

암튼 이 문제는 인풋이 더럽게도 2차원 배열로 주어집니다. 것도 그래프가요. 따라서 저는 List 배열로 예쁜 그래프를 만들어놓고 문제를 풀었습니다.

 

걍 뭐... 겁나게 단순합니다. 총 몇 개의 네트워크가 있냐 == BFS 타고 들어갈 수 있는게 몇 개냐 라고 볼 수 있습니다.

고로 visited[] 체크를 하면서 방문한 적이 없는 노드(컴퓨터)가 있다면 걔는 이전 네트워크들과는 별개의 네트워크를 형성하니깐 answer++ 되는 것이지요.

 

나중에 여유가 생기고 하고 싶은 맘이 생기면 릿코드도 시작해야겠습니다.

 

하지만 역시 노는게 제일 좋아~~

 

그럼 20000