프로그래머스 - 네트워크

lv. 3 단계의 코딩 테스트 연습 문제 중 '네트워크'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 네트워크

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 프로그래머스에서 처음으로 푼 lv. 3 문제인데, 확실히 난이도가 뒤죽박죽인 것 같다.
• 단순히 BFS를 사용하면 아주 쉽게 풀 수 있는 문제였다.
• 문제는 결국 서브 그래프 수를 구하는 것이다.
• 주어진 행렬 형태에서 그래프를 탐색하는 것이 귀찮아서, 딕셔너리를 이용해서 그래프를 사용하기 편한 형태로 바꿨다.
  • 예를 들어, 1 노드가 3, 5와 연결되어 있으면,
  • 1: [3, 5] 와 같은 식으로 표현했다.
• 이후에 1번 노드부터 BFS를 돌고 1번 노드와 연결된 모든 노드들을 방문 체크를 했다.
• 이제 2번 노드부터 N번 노드까지 탐색하면서 방문하지 않은 노드가 있으면, 해당 노드를 기준으로 다시 BFS를 돌리면서 방문 체크를 했다.
• 이 과정을 계속 반복하면 되고, BFS를 돌린 횟수가 서브 그래프의 수가 되며 결국 정답이다.
• 코드는 아래와 같다.

코드

from collections import defaultdict, deque
def solution(n, computers):
    answer = 0
    
    graph = defaultdict(list)
    for idx, row in enumerate(computers):
        for j in range(len(row)):
            if idx != j and row[j] == 1:
                graph[idx].append(j)
                
    visited = [False for _ in range(len(computers))]
    
    for i in range(len(visited)):
        if not visited[i]:
            answer += 1
            q = deque()
            q.append(i)
            while q:
                x = q.popleft()
                if visited[x]:
                    continue
                visited[x] = True
                
                for next in graph[x]:
                    q.append(next)
            
    return answer

 

BFS는 이제 정말 쉽게 구현할 수 있다. 이제 다른 유형으로 넘어갈 예정이다.

 

추천글

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

프로그래머스