[Python] 프로그래머스 네트워크 | BFS/DFS

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

문제 해결 포인트

모든 노드를 탐색하여야 하기 때문에 DFS/BFS 둘 다 사용하여 구현할 수 있습니다.

하지만 Python은 DFS 효율이 좋지 않기 때문에 BFS를 추천드립니다.

 

BFS

- 모든 노드가 연결되지 않았기 때문에 한 번 BFS를 돌고 난 뒤 아직 방문하지 않은 노드를 다시 찾아야 함

- 아직 방문하지 않은 노드를 발견한다면 queue에 삽입하여 BFS를 수행하여 해당 네트워크 노드에 대해 전부 방문처리(visited)

- 각 노드 별 computers 리스트 값에서 본인과 연결되어 있으면서(1이면서) 아직 방문하지 않은(visited가 False) 노드(i)를 삽입

- 모든 노드를 방문할 때까지 반복하면 네트워크를 하나 끝낸것이다. 

 

DFS

- 방문한 노드는 set 자료구조에서 관리

- 큰 틀에서 방문하지 않은 모든 노드를 확인 ( 네트워크 )

- 재귀함수를 함수 내부에 구현함으로 visited 접근 가능

- DFS를 끝내고 돌아왔다 = 네트워크 하나 돌고 왔다

 

 

작성 코드

BFS

from collections import deque


def solution(n, computers):
    que = deque()
    visited = [False] * n
    count = 0

    for vertex in range(n):
        if not visited[vertex]:  # 아직 방문하지 않은 시작 노드
            # BFS
            que.append(vertex)
            while que:  # queue에 값이 있는 동안
                q = que.popleft()
                visited[q] = True  # 방문 표시
                for i, v in enumerate(computers[q]):  # 만약 computer[q][i] = 1이라면 연결됨
                    if not visited[i] and v:  # 연결된 node가 방문하지 않았다면
                        que.append(i)
            count += 1  # 한 네트워크 완료
    return count


print(solution(3,	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))  # 1
print(solution(3,	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]))  # 2

 

DFS

def solution(n, computers):
    visited = set()
    answer = 0

    def dfs(computer):
        for i, c in enumerate(computers[computer]):
            if i not in visited and c:
                visited.add(i)
                dfs(i)

    for c in range(len(computers )):
        if c not in visited:
            visited.add(c)
            dfs(c)
            answer += 1

    return answer

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚