[프로그래머스] 네트워크-BFS/DFS lv.3 (Python3)

제가 그래프에 많이 약해서 그래프 좀 풀어보겠습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/43162

 

네트워크

 

2차원 배열이 있고, 각 열마다 어떤 번호와 연결되어 있는지 1, 연결되어 있지 않은지 0으로 표시합니다.

 

A-B, B-C 연결에서 A와 C는 B를 통해 간접적으로 연결됩니다.

 

이런 간접 연결을 포함해서 같은 네트워크 상에 있는 컴퓨터의 최대 개수를 구합니다

 

BFS 기본 구조는

 

from collections import deque로 deque를 불러오고

일단 q에 첫 번째 원소를 집어넣고

while q를 돌려서 q가 빌떄까지 계속한다

그 안에서 for문을 돌려 q에서 popleft 한 원소에 대해

그 원소 주변에 있는 조건에 해당하는 원소를 살피고

조건에 해당하면 q에 추가한다.

 

위 구조가 bfs 함수의 구조이고,

main 함수에서 for문으로 bfs 문을 탐색한다

 

이 구조가 항상 헷갈리는데

 

일단 bfs 함수 따로 만들고

 

main 함수에서 bfs 함수를 불러와서 실행하는 방식으로 이해하면 된다고 생각한다

 

디테일은 풀면서 계속 잡아나가자

 

from collections import deque
def solution(n, computers):
    def bfs(start):
        q = deque([start])
        visited[start]=True
        while q:
            node = q.popleft()
            for neighbor in range(n):
                if computers[node][neighbor]==1 and not visited[neighbor]:
                    visited[neighbor] = True
                    q.append(neighbor)
    visited = [False]*n
    answer=0
    
    for i in range(n):
        if not visited[i]:
            bfs(i)
            answer+=1

    
    return answer

 

컴퓨터는 n개, 각 컴퓨터를 순차적으로 탐색하며 bfs를 돌려준다

 

이때 2차원 배열은 A,B 두 컴퓨터에 대해 (A,B) 또는 (B,A)의 연결관계를 모두 가지고 있어서

같은 연결을 두 번 탐색해 네트워크 길이 측정에 오류를 범할 수 있기 때문에!

 

visited 배열에서 이미 방문한 컴퓨터가 아닌 경우에만 bfs 함수를 돌린다.

---

 

bfs는 각 컴퓨터 번호를 q에 첫번째 원소로 넣어 탐색을 시작한다

 

q.popleft() (큐에 가장 먼저 삽입된 원소)를 기준으로, 해당 원소의 이웃들을 점검한다

만약 해당 원소가 어떤 이웃과 연결되어 값이 1이고, 방문한적이 없다면

 - 방문했다고 True로 갱신, 그리고 해당 원소를 q에 추가한다

 

위 세 줄을 반복해서 q에 더이상 추가될 원소가 없으면 while문은 종료된다

 

---

 

다시 main의 for문 안으로 돌아와서 answer를 1 증가시킨다

또 다시 다음 컴퓨터 번호에 대해 for문이 시작된다.

 

---

 

for문이 끝나면 answer를 return한다

 

 

---

 

티스토리 블챌이 시작되었는데

21일 동안 꾸준히 해야하는 만큼...

 

꾸준히 풀어야 하는 코테로 해보겠습니다..

 

그 사이사이 늘 올리던 대로 컴파일러 정리도 올라갈 예정

근데 나 프엔 백엔 글감은 밀려있는데 정작 못올리고 있다...