[programmers] python DFS/BFS 네트워크

 

programmers.co.kr/learn/courses/30/lessons/43162?language=python3

코딩테스트 연습 - 네트워크

 

 

< problem >

 

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

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

 

< constraints >

- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
- i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
- computer[i][i]는 항상 1입니다.

 

---

 

< example >

 

- example 01) 2개의 네트워크가 있음

 

- example 02) 1개의 네트워크 있음

 

---

 

BFS(Breadth First Search)

- 모든 단계에서 가능한 모든 경우의 수 확인하는 탐색 방법

- 첫 번째, 두 번째, ... 가능한 모든 것을 확인하며 천천히 깊어지는 탐색, 큐 활용

 

DFS(Depth First Search)

- 스택 활용하여 한 우물만 파서 끝까지 가는 탐색 방법

 

참고 link: jeinalog.tistory.com/18

참고 link : itholic.github.io/python-bfs-dfs/

 

---

 

< solution ① > queue, BFS 활용

 

- 네트워크 개수 return 위한 변수 network, 탐색 시 저장 할 큐 q, 탐색했는지 여부 파악 위한 배열 visited 선언

    - 처음에는 방문한 곳이 없기 때문에 visited는 0으로 초기화

- 탐색 시작

    - 0번째 index를 q에 추가하고, visited[0] = 1 : 이 과정은 세트로 고정

    - q에 저장되어 있는 컴퓨터가 있다면 변수 c에 pop하여 대입

        - 방문하지 않고, 연결되어 있다면 q.append( ) + visited = 1

    - while문이 끝나면 network + 1

- return network

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

---

- while q: 조건의 경우 q에 아무것도 없으면 바로 끝나기 때문에 모든 return 값은 1로 동일할 것임 

    →  모든 computer를 탐색하며 network 수 파악 위해 while문 추가

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

---

- while문이 추가되어 실행 시간도 더 길어지는 것으로 예상

    → while문 반복 시 매번 모든 computer 방문하는 것이 아니라 visited가 0인 경우만 q에 추가

        - index함수 사용하여 값이 0인 index 변수 v에 저장 + q.append(v) + visited[v] = 1

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

---

- 함수로 묶어서 재귀를 활용하면 좀 간단해질까 해서 시도

 

ⓒ ⓞ ⓓ ⓔ

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

---

- 마지막으로 len(graph[k])를 재귀로 부를 때, 반복문 실행 시에 모두 계산이 들어갈 것이 예상되어 변수로 선언

 

ⓒ ⓞ ⓓ ⓔ

 

ⓣ ⓔ ⓢ ⓣ

---

 

< solution ② > DFS 활용

- BFS 활용한 solution ① 코드와 큰 차이는 없음

 

- 하나의 차이점은 방문하지 않고, 연결되어 있다면 반복하여 탐색하기

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

ⓕ ⓘ ⓝ ⓐ ⓛ    ⓒ ⓞ ⓓ ⓔ

 

BFS는 내가 처음 생각해 낸 방법이기 때문에 final은 BFS 활용했던 코드로 !

 

 

---

ⓒ ⓞ ⓜ ⓜ ⓔ ⓝ ⓣ

 

여러 글들을 참고해보고 강의도 들어보았지만, 

탐색에 있어서는 많은 문제를 풀어보고 직접 부딪히며 이해하는 것이 가장 빠를 것 같음

우선 큐를 활용한 방법이 더 편리하고 익숙하여 먼저 해보지만, 

스택 활용한 DFS도 공부해봐야함