[🥲 프로그래머스] 네트워크 - BFS/DFS

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

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

 

✅ 내가 푼 풀이

# 1차시도 -> 92.3점
def solution(n, computers):
    graph = {i:[] for i in range(n)}
    stack = [1]
    visited = []
    
    # 그래프 형식으로 생성
    for net in range(len(computers)):
        for num in range(len(computers[net])):
            if computers[net][num] == 1 and net != num:
                graph[net].append(num)
                
    count = 0 # 네트워크 갯수
    network = [] # 연결된 컴퓨터id 넣기
    all_number = [i for i in range(n)] # n까지의 모든 수, 연결되지 않은 애들을 위한 코드

    while stack:
        node = stack.pop()
        if node in all_number:
            all_number.remove(node)
        
        # node가 0 -> 시작
        if node == 0:
            network.extend(graph[node])
        
        # 해당 노드가 방문하지 않은 노드일 경우
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node])
            
            if node in network:
                network.extend(graph[node])
            else:
                # node가 notwork에 있지 않으면 더 이상 연결된 network가 아니라는 뜻
                # 여태까지 네트워크 +1, network 리스트 초기화 후 현재 node의 value를 넣어준다. 
                count += 1
                network = []
                network.extend(graph[node])
                
        # 아무데도 연결되지 않은 node를 처리하기 위한 코드
        if not stack and len(visited) != n:
            stack.append(all_number[0])
    return count

테스트 케이스 중 하나가 런타임 에러 발생

 

✅ 다른 분 풀이

def solution(n, computers):
    answer = 0
    queue = []
    visited = [0]*n
	# 아직 방문하지 않은 노드가 있으면
    while 0 in visited:
        x = visited.index(0) # 해당 노드 찾아서 x에 입력
        queue.append(x) # queut에 더해줌
        visited[x] = 1 # 방문했다고 변경
        
        while queue:
            node = queue.pop(0)
            visited[node] = 1
            for i in range(n):
            	# 아직 방문하지 않았고 & 네트워크가 연결되어 있다면
                if visited[i] == 0 and computers[node][i] == 1:
                    queue.append(i)
                    visited[i] = 1
        answer += 1
    return answer