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

문제

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

사용 알고리즘

- BFS (너비우선탐색)

해결방법

• 0 ~ 200 까지의 그래프를 BFS를 통해 몇 개의 네트워크가 존재하는지 찾는다
• bfs를 한 번 돌 때마다 연결된 노드들은 visited = true 체크가 되므로, bfs 실행 횟수가 네트워크 개수가 됨

소스코드

사용언어 : Java

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        
        for (int i=0; i<n; i++) {
            if (!visited[i]) {
                bfs(computers, visited, i);
                answer++;
            }
        }
        
        return answer;
    }
    
    public void bfs(int[][] computers, boolean[] visited, int start) {
        Deque<Integer> q = new ArrayDeque<>();
        visited[start] = true;
        q.offer(start);
        
        while (!q.isEmpty()) {
            int current = q.removeFirst();
            int[] row = computers[current];
            
            for (int i=0; i<row.length; i++) {
                if (row[i] == 1 && !visited[i]) {
                    visited[i] = true;
                    q.addLast(i);
                }
            }
        }
    }
}

boolean[] visited = new boolean[n]

• n개의 요소를 false로 가진다 (JVM이 배열 요소를 기본값으로 0/false/null로 초기화)
• int[] -> 0으로 초기화
• double[] -> 0.0으로 초기화
• char[] -> '\u0000'
• Object[] / String[] / Boolean[] 등 참조 타입 배열 -> null로 초기화

 

 

Queue

• FIFO 
• 넣기 : add() / offer()
• 빼기 : remove() / poll()
• 들여다보기 : element() / peek()
  -> add / remove / element : 실패 시 예외
  -> offer / poll / peek : 실패 시 false/null 반환
• [구현체]
  • ArrayDeque(권장, 비동기) - 빠르고 가벼운 원형 버퍼
  • LinkedList - 노드 기반, 오버헤드 큼
  • PriorityQueue - 우선순위 큐 O(log n)
  • 동시성 용 : ConcurrentLinkedQueue(lock-free), LinkedBlokingQueue/ArrayBlockingQueue 등

 

Deque

• 양쪽 끝에서 넣고 빼는 큐. FIFO, LIFO 둘 다 구현 가능
• 넣기 : addFirst / offerFirst, addLast / offerLast
• 빼기 : removeFirst / pollFirst, removeLast / pollLast
• 보기 : getFirst / peekFirst, getLast / peekLast
• 스택 스타일 : push() (=addFirst), pop() (=removeFirst)
• [구현체]
  • ArrayDeque(권장)
  • LinkedList
  • 동시성 용 : ConcurrentLinkedDeque

---

 

무엇을 언제 ?

• 일반 FIFO 큐: ArrayDeque
• 스택: ArrayDeque(push/pop)
• 우선순위 필요: PriorityQueue
• 생산자-소비자(블로킹): LinkedBlockingQueue/ArrayBlockingQueue (put/take, offer with timeout)
• 멀티스레드(락 없이 비차단): ConcurrentLinkedQueue / ConcurrentLinkedDeque

 

 

 

성능/특징 한눈에

• ArrayDeque: 배열 기반 원형 버퍼, 양끝 암묵적 O(1), 객체 노드 없음 → 보통 가장 빠름
• LinkedList: 양끝 O(1)이지만 노드 할당/GC 비용, 캐시 비우호적
• PriorityQueue: 힙 구조, 삽입/삭제 O(log n)
• 대부분 구현체는 스레드-안전하지 않음 → 필요 시 동시성 큐 사용

 

 

 

실수 방지 포인트

• 빈 큐에서 remove()/element() → 예외, poll()/peek() → null
• ArrayDeque/Deque null 금지
• BFS/레벨 순회 등 큐가 필요한 알고리즘엔 ArrayDeque 권장 (LinkedList보다 가볍고 빠름)

 

---

한줄평

자바로 코테 준비하기 시작..! (문법을 잘 몰라서 너무 힘들다 흑흑 ㅠㅠ)