프로그래머스 네트워크 C++

 

 

컴퓨터 a와 b가 직접적으로 연결이 되어져 있고, b와 c가 직접적으로 연결이 되어있다.

또한 a와 c는 간접적으로 연결이 되어있어 서로 정보를 교환할 수 있기에, abc는 같은 네트워크에 있다고 본다.

 

이러한 구조를 형성할 수 있는 컴퓨터 n개 ( 1~200 이하)

연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어졌을 때

네트워크의 개수를 반환해라

 

각 컴퓨터는 0~ n-1인 정수로 표현하며,

i번과 j번이 연결되어있다면 computer[i][j] = 1로 표현한다

i i번은 항상 1로 표시

 

즉 예시로 보자면 110 110 001에서 1번과 2번은 연결되어져있지만 3은 아니기에 생성된 네트워크의 개수를 2개이고

 두번 째 예시에서는 110 111 001은 세개다 이어져있기에 생성된 네크워크는 1개이다.

 

dfs를 이용해 깊이 탐색을 하며, 방문 체크를 해주고

방문하지 않은곳(새로운 네트워크)을 방문할 경우에 개수를 세어주면

서로 이어지지 않은 네트워크의 개수를 셀 수 있게 된다.

 

반복문을 통해 컴퓨터의 개수 만큼 반복을 하여주고

방문이 아직 안되어있는 경우 dfs함수를 만들어 호출해준다

dfs안에서 방문이 아직 안되어져있으며, 연결되어져있는 컴퓨터를 발견하면 재귀 호출을 통해 이어져있는 컴퓨터를

계속하여 탐색하며 방문체크를 하여준다.

 

그러다 재귀 호출이 종료되면 다시 본문으로 돌아와 다음 노드를 검사하며 방문하지 않은 컴퓨터를 발견했다면

새로운 네트워크발견으로 다시 dfs를 호출하며 깊이 탐색을 하나씩 진행하며 끝날때마다 answer 반환값에 ++을 해준다.