[Python] 프로그래머스 구명보트 & 프로그래머스 네트워크

구명보트

#프로그래머스 구명보트

def solution(people, limit):
    cnt = 0
    people = deque(sorted(people))
    while people:
        person = people.pop()

        if people and person + people[0] <= limit:
            people.popleft()
            
        cnt += 1

    return cnt

큐 + 그리디로 해결

 

네트워크

from collections import deque

def solution(n, computers):
    visited = [False] * (n+1)
    graph = [[] for _ in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if i != j and computers[i][j] == 1:
                graph[i].append(j)
                graph[j].append(i)

    cnt = 0
    for i in range(n):
        if not visited[i]:
            cnt += bfs(graph, visited, i)
    return cnt

def bfs(graph,visited, start_node):
    queue = deque()
    queue.append(start_node)
    visited[start_node] = True
    while queue:
        current_node = queue.popleft()
        for next_node in graph[current_node]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node] = True
                
    return 1

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

처음에는 정답으로 전체 visited개수를 셌는데 실패...ㅠㅠ

만약 컴퓨터 개수가 5개이고 3개 2개로 연결돼있으면 네트워크 개수는 총 2개인데 이 경우를 생각치 못해서 좀 헤맸다ㅠㅠ 전체 컴퓨터를 돌면서 만약 방문을 안했으면 bfs()돌고 반환값을 1로 해서 총 네트워크의 개수를 세줬다.