[Python] 네트워크

 

 

DFS & BFS 개념 ☞ 2021.06.20 - [Algorithm/개념] - DFS / BFS

 

1.  DFS

def DFS(n, com, visited, computers) :
    visited[com] = True
    
    for j in range(n) :
        if com != j and computers[com][j] == 1:
            if visited[j] == False :
                DFS(n, j, visited, computers)


def solution(n, computers):
    visited = [False for i in range(n)]
    answer = 0
    
    for com in range(n) :
        if visited[com] == False :
            DFS(n, com, visited, computers)
            answer += 1
            
    return answer

---

풀이

1. 네트워크 수 (n)만큼  False로 채운 리스트를 만든다.

2. for문을 통해 해당 번호의 컴퓨터가 방문이 안되어있다면 방문 처리(True)하고, 그 컴퓨터와 연결되어있는 컴퓨터를 방문한다. 

3. 이를 재귀함수를 통해 반복하며, 반복이 끝났을 경우에는 같은 네트워크상에 있는 컴퓨터는 다 방문한 것이므로  answer + 1 해준다.

4. 이렇게 모든 컴퓨터를 방문하면 끝이 난다. 

 

---

 

2.  BFS

def BFS(n, computers, com, visited):
    visited[com] = True
    queue = []
    queue.append(com)
    while queue :
        com = queue.pop(0)
        visited[com] = True
        for connect in range(n):
            if connect != com and computers[com][connect] == 1:
                if visited[connect] == False:
                    queue.append(connect)
                    
def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            BFS(n, computers, com, visited)
            answer += 1
    return answer

 

---

풀이

1. 네트워크 수 (n)만큼  False로 채운 리스트를 만든다.

2. for문을 통해 해당 번호의 컴퓨터가 방문이 안되어있다면 방문 처리(True)하고, (여기까진 DFS랑 같음)

    해당 번호를 queue에 추가한다.

3. while문을 통해 queue에 있는 번호의 컴퓨터는 방문처리(True)해줄건데, 

   해당 컴퓨터가 받은 번호(com)와 연결되어있고, 방문하지 않은 컴퓨터라면 queue에 추가해준다. 

4. 이를 반복하고, 모든 컴퓨터를 방문하면 끝이 난다.