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

반응형
반응형

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

이 문제는 사이클의 갯수를 구하는 문제이다.
예를들어

이런 그래프가 있다고 가정해보자.
그리고 연결되어 있는 노드의 갯수를 세보자
정확히 2개가 나온다. 왜냐하면 노드 1과 노드 2가 연결이 되어 있고
노드 3은 아무것도 연결이 되어있지 않기 때문이다.
그러면 어떤 알고리즘을 사용해서 문제를 풀어야 할까?

간단히 생각해보자.
1번 노드에서 2번 노드로 값을 전달한다.
그상태에서는 1번 노드에 방문한 셈이 된다.

 visited[start] = true;

이제 반복문을 사용하던지 아니면 제귀를 사용해서 다음 노드로 값을 넘겨 보자.

코드를 작성해보면...

for (int next = 0; next <= total; next++) {
            if (visited[next]) continue;
            if (computers[current][next] == 1) {
                dfs(next, total, computers);
            }
}

이런식으로 작성할 수 있다.
만약, 다음 노드를 검색했는데 이미 방문하였다면? 
그곳은 넘어가게 된다.

근데 생각해보자.

위 그림에서는 3번 노드도 존재하는데
코드에서는 3번으로 넘어갈시 어떻게 될까?

애석하게도 dfs가 동작하지 않는다. 왜나하면 1,3 // 2,3은 0이기 때문이다.
그렇기 때문에 stack overflow의 걱정은 하지 않아도 된다.

자 이제 거의 끝났다.

마지막으로 생각해 볼것은

3번 노드 즉, 3,3은 어떻게 되는 걸까?

여기서도 조건을 입력해줘야한다.

바로 방문을 했는지 확인할 필요가 있다.

for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            dfs(i, n, computers);
            count++;
}

이렇게 코드를 작성하면

1번 노드 2번 노드가 방문이 되었는지 확인하고

dfs를 돌리면 정삭적으로 동작하게 된다.

그러면 어째서 이차 배열이 아니라 그냥 일차 배열일까?

결론부터 말하면 1번노드에서 2번 노드로 가는 그 간선의 방문을 물어보는 것이 아니라

노드의 방문을 물어보는 것이기 때문에 이차 까지 갈 필요는 없다.

 

반응형

댓글

Designed by JB FACTORY