[programmers] 네트워크

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

프로그래머스

 

---

< 네트워크 >

 

문제 풀이 (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]) {
				answer += 1;
				visited[i] = true;
				bfs(i, computers, visited);
			}
		}

		return answer;
	}

	private void bfs(int idx, int[][] computers, boolean[] visited) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(idx);

		while (!queue.isEmpty()) {
			int num = queue.poll();

			for (int i = 0; i < computers.length; i++) {
				if (num == i) {
					continue;
				}
				if (computers[num][i] == 1 && !visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}
}

 

모든 컴퓨터를 탐색하며 아직 네트워크가 이뤄지지 않은 컴퓨터라면 네트워크 추가, 방문 표시, bfs 함수를 호출한다. 최종 answer을 반환한다.

 

bfs 함수에서는 Queue에 시작 컴퓨터 번호를 저장한 후 Queue가 빌 때까지 다음 과정을 반복한다.

1. queue poll

2. 현재 컴퓨터에서 연결된 컴퓨터 중 아직 네트워크를 이루지 않은 컴퓨터가 있는지 확인한 후, 있다면 방문 표시 및 queue에 저장한다.

 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges