43162: 네트워크[DFS/BFS]

Link : programmers.co.kr/learn/courses/30/lessons/43162

---

1. 문제

• 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
  컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

---

2. 문제의 조건

• 1 <= n <= 200
• i와 j가 연결 되어있으면 computer[i][j] = 1 로 표현

 

---

3. 문제 접근

• 시간 복잡도
  
  추후보강

 

• 아이디어
  
  주어진 인접행렬 정보를 인접리스트로 바꾸어 그것으로 DFS로 탐색하는 아이디어를 떠올렸습니다.
  
  처음엔 겹친 부분의 network을 del하여 줄여갔더니  4, [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]]
  다음과 같은 엣지케이스가 발생하였습니다. 그래서 삭제하지말고 같은 레벨에 있는 것들은 레벨끼리 묶기로 하였습니다.

 

---

4. 풀이 방법

• 인접행렬을 인접리스트로 변환합니다.
  해당 케이스는 중복을 줄이기위해 dict에 set으로 적용하였습니다.
• 각 네트워크를 dict로 생성합니다.
• 인접리스트에 존재하는 모든 지점을 방문합니다.
  탐색을 시작하는데 아직 방문하지 않은 장소가 있다면 레벨을 표시해주고
  한번 더 DFS를 수행합니다.
• DFS가 끝나면 레벨 단위로 표시가 되어있고, -1은 아직 방문하지 않은 네트워크이므로 독립적인 네트워크가 됩니다. -1인 것들은 따로 개수를 세준 다음
  같은 레벨에 존재하는 것들의 개수를 함께 더해줍니다.

 

---

5. 소스코드

• cjw-git.tistory.com/104

---

 

cjw.git@gmail.com