프로그래머스 네트워크

computers의 각 원소는 컴퓨터이므로 컴퓨터마다 돌면서 연결된 컴퓨터들을 체크하면 된다.

queue를 활용한 BFS를 적용한 check_com으로 초기에 선택한 컴퓨터에 연결된, 아직 체크되지 않은 모든 컴퓨터에 대해서 체크해준다. 이 컴퓨터는 queue에 들어간다.

queue가 빌 때까지 check_com을 계속 호출하면 연결된 네트워크를 찾을 수 있다.

 

나머지 컴퓨터에 대해서 검사를 하는데 이미 체크된 것은 특정 네트워크에 속한 것이므로 검사할 필요가 없다.

체크되지 않은 컴퓨터가 있다면 answer를 증가시키고 컴퓨터를 queue에 넣고 check_com을 호출한다.

 

결론은

컴퓨터 하나하나를 트리의 root로 생각하고 방문하지 않았으면 answer를 증가시키고 연결된 컴퓨터(노드들)를 방문하는 것이다.

answer = 0
checker = []
queue = []


def check_com(computers):
    global queue, answer
    while queue:
        i = queue[0]
        del queue[0]
        for j, com in enumerate(computers[i]):
            if com and not checker[j]:  # 연결이 있으면서, 검사 안한 컴퓨터
                checker[j] = True
                queue.append(j)
        check_com(computers)
    return


def solution(n, computers):
    global checker, queue, answer
    answer = 0
    checker = [False] * n
    for i, com in enumerate(computers):  # 컴퓨터 한 대씩 검사
        if not checker[i]:
            answer += 1
            queue.append(i)
            check_com(computers)
    return answer

 

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

코딩테스트 연습 - 네트워크 | 프로그래머스