🔍 Problem
📃 Input&Output
🌁 문제 배경
가. 문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.
나. 접근 방법
방문하지 않은 노드들을 순회하여 BFS 돌리고, 하나의 BFS 주기가 끝나면 네트워크 개수를 하나 증가시킨다.
다. 문제 유형
BFS
📒 수도 코드
가. for문 0 ~ number-1 순회
나. for 문 i 값의 vst[i]가 false면, 새로운 큐 생성 후 넣기
다. 큐가 빌때까지 아래 반복
- 큐에서 하나씩 꺼내서
- 꺼낸 노드와 연결된 노드 큐에 넣고 방문처리
❓ 방문 처리를 이때 하는 이유
방문 처리를 이때 안해주고 큐에서 노드 뺄때 해주면 문제가 발생한다.
왜냐하면 이전의 상황에서 들어간 노드들 사이에 연관관계가 있는 경우, 큐에 이미 들어갔지만, 방문처리가 되지 않아(아직 나오지 않았기 때문에) 한번 더 큐에 들어갈 수 있는 상황이 생기기 때문이다.즉, 큐에 중복된 값이 들어갈 수 있기 때문이다.
라. 큐가 비었으면 ans++
💻 Code
import java.util.*;
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
Queue<Integer> que ;
boolean[] vst = new boolean[n];
for (int i=0; i<n; i++){
if(vst[i]==false){
//bfs
que = new LinkedList<>();
que.add(i);
vst[i]=true;
while(!que.isEmpty()){
int node = que.poll();
for (int j=0; j<n; j++){
if(vst[j]==false && computers[node][j]==1){
que.add(j);
vst[j]=true;
}
}
}
answer++;
}
}
return answer;
}
}
/*
*/🎸 기타
가. 풀이 시간
25분
🦭 코드 리뷰
가. Queue 변수 재사용 가능
que는 while문 안에서 다 소모되므로, 클래스 전체에서 하나만 선언해도 무방
Queue<Integer> que = new LinkedList<>();나. 변수명 명확하게
que→queuevst→visited
다. 불필요한 공백 줄 정리
코드에 과도한 빈 줄이 있어 읽기 흐름이 끊김
개선된 코드
import java.util.*;
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
Queue<Integer> queue = new LinkedList<>();;
boolean[] visited = new boolean[n];
for (int i=0; i<n; i++){
//bfs
if(visited[i]==false){
queue.add(i);
visited[i]=true;
while(!queue.isEmpty()){
int node = queue.poll();
for (int j=0; j<n; j++){
if(visited[j]==false && computers[node][j]==1){
queue.add(j);
visited[j]=true;
}
}
}
answer++;
}
}
return answer;
}
}
🤔 느낀점
오랜만에 BFS Queue에 노드를 넣을 때, 방문처리를 언제하는지 고민하게 하는 문제였고, 이는 필자의 BFS 숙지 미숙을 의미한다. 이에 해당 증명을 확실히 해야한다는 것을 느꼈고 큐에 중복된 노드가 들어 갈 수 있음을 방지하기 위해, 큐에 노드를 넣을 때 방문처리를 한다 라고 증명을 정리하였다. 해결 시간은 25분으로 준수하다고 생각한다. 필자는 현재 30분 이내에 한문제 푸는 것을 연습중이기 때문이다.
