[Programmers] 네트워크 (DFS/BFS Lv.3) - Python

1. 문제

---

타겟 넘버

2. 풀이

---

코드

def bfs(start):
    queue = [start]
    visited[start] = True

    while queue:
        node = queue.pop(0)
        
        if adjacency_list[node]:
            for neighbor in adjacency_list[node]:
                if not visited[neighbor]:
                    queue.append(neighbor)
                    visited[neighbor] = True
    
    return 1


def solution(n, computers):
    global visited
    global adjacency_list
    visited = [False] * n
    adjacency_list = [[] for _ in range(n)]
    group_count = 0
    
    for i in range(n):
        for j in range(n):
            if i != j and computers[i][j] == 1:
                adjacency_list[i].append(j)
    
    for i in range(n):
        if not visited[i]:
            group_count += bfs(i)
    
    return group_count

입력 및 출력

computers	= [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
n = 3

>> 2

3. 로직

---

1. bfs 함수는 너비 우선 탐색(BFS)을 수행한다. start는 시작 노드, visited는 방문한 노드를 표시하는 리스트, adjacency_list는 인접 리스트를 나타내는 리스트이다. 함수는 start 노드부터 BFS를 시작하여 해당 네트워크의 노드를 모두 방문하고, 방문한 노드의 개수인 1을 반환한다.

2. solution 함수는 주어진 컴퓨터의 개수 n과 연결 상태를 나타내는 computers 리스트를 인자로 받는다. 먼저 방문 여부를 저장하는 visited 리스트와 인접 리스트를 나타내는 adjacency_list를 초기화한다. 그리고 computers를 순회하면서 연결된 노드들을 adjacency_list에 추가한다.

3. 이후 visited 리스트를 확인하여 방문하지 않은 노드가 있다면 해당 노드부터 BFS를 수행하고, BFS 결과로 반환된 그룹의 개수를 group_count에 더한다.

4. 마지막으로 group_count를 반환하여 네트워크의 개수를 출력한다.

4. 그림

---