문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.
입출력 예
입출력 예 설명
예제 #1
아래와 같이 2개의 네트워크가 있습니다.
예제 #2
아래와 같이 1개의 네트워크가 있습니다.
코드
function solution(n, computers) {
var answer = 0;
var check = [];
check.length=200;
check.fill(0);
function dfs(idx){
check[idx]=1;
for(let j=0; j<n; j++){
if(check[j]==0 && computers[idx][j]==1){
dfs(j);
}
}
}
for(let i=0; i<n; i++){
if(check[i]==0){
dfs(i);
answer++;
}
}
return answer;
}
풀이
컴퓨터의 개수는 200대까지 이므로 길이가 200인 check배열을 만들어 0으로 초기화시켜준다.
여기서 check배열은 노드를 확인했다고 표시하는 용도로 쓰인다.
예시 1번을 봐보자.
n=3, computers =[[1,1,0],[1,1,0],[0,0,1]]
처음에는 1번 노드를 확인했는지 체크한다.
1번 노드를 아직 확인하지 않았으므로(check[0]=0이므로) dfs함수를 실행시켜준다.
dfs함수를 실행하자마자 1번 노드를 확인한 것이 되므로 check[0]=1이다.
이후 컴퓨터의 개수 만큼 for문을 돌려주어, 1번 컴퓨터와 j번 컴퓨터가 연결되었는지 확인한다.
j를 0부터 돌리는 이유는, computers[j][j]가 1이기 때문이다.
컴퓨터가 항상 자기자신과 연결되어있다고 이해해도 될 것 같다.
dfs내의 for문이 돌아가면서,
만약 j번째 컴퓨터를 아직 확인하지 않은 상태이며, 현재 컴퓨터가 j번째 컴퓨터와 연결되어 있다면,
j번째 컴퓨터를 확인해본다. = dfs(j)
더 이상 연결된 컴퓨터가 없을 때에 dfs함수가 종료될 것이고, 이후 answer에 1을 더해줄 것이다.
(dfs함수가 종료되면 네트워크 하나를 확인한 것이기 때문)
다시 한 번 정리하자면,
- 내가 이 컴퓨터의 네트워크를 확인했는가? => YES: - / NO: 2번(function dfs)
- 이 컴퓨터와 j번째 컴퓨터가 연결되어 있고, j번째 컴퓨터의 네트워크를 확인한 상태인가?=> YES: 3번 / NO: answer++
- n회 반복
처음 코드를 작성할 때 for문의 i와 j를 따로 선언해주지 않고
for(i=0; i<n; i++){}
이렇게 작성하였는데 13개의 테스트 케이스 중 9개를 틀렸다.
코드를 계속 살피다가 i와 j를 let으로 선언해주었더니 테스트 케이스 전부를 맞을 수 있었다.
다른 문제에선 아무 문제없이 잘 돌아갔는데 해당 문제에선 왜 이러한 문제가 생긴 것인지 공부해보아야겠다.
