[프로그래머스]네트워크

[43] 네트워크

책 구매하기

문제 정보

• 분류: 그래프
• 정답률: 59%
• 권장 시간 복잡도: O(N^2)
• 핵심 키워드: DFS, 연결 요소, 인접 행렬, 네트워크 수
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제를 읽을 때 체크할 포인트

결국 연결 요소 개수를 세는 문제다. 아직 방문하지 않은 컴퓨터에서 DFS나 BFS를 한 번 시작할 때마다 네트워크 하나를 찾은 셈이다.

최단 거리나 연결성처럼 칸과 칸, 정점과 정점 사이를 따라가야 하는 문제는 결국 탐색 구조가 핵심이다. 방문 상태를 어떻게 정의하느냐가 정답을 거의 결정한다.

풀이 흐름

1. visited 배열을 둔다.
2. 각 컴퓨터를 보면서 아직 방문하지 않았다면 탐색을 시작한다.
3. 탐색을 시작한 횟수를 세어 반환한다.

구현할 때 놓치기 쉬운 부분

연결된 컴퓨터를 한 번 탐색한 뒤에는 그 안의 노드를 다시 시작점으로 세면 안 된다. 연결 요소 개수를 세는 문제라는 점을 놓치지 않고 방문 배열을 분명히 두어야 한다.

파이썬 정답 코드

def solution(n, computers):
  # visited 배열을 둔다.
  visited = [False] * n

  def dfs(start):
    stack = [start]
    visited[start] = True

    while stack:
      cur = stack.pop()
      for nxt in range(n):
        if computers[cur][nxt] == 1 and not visited[nxt]:
          visited[nxt] = True
          stack.append(nxt)

  answer = 0
  # 각 컴퓨터를 보면서 아직 방문하지 않았다면 탐색을 시작한다.
  for i in range(n):
    # 탐색을 시작한 횟수를 세어 반환한다.
    if not visited[i]:
      dfs(i)
      answer += 1

  return answer

시간 복잡도

N은 컴퓨터 수이다.

기준 원소마다 다른 원소를 다시 보거나, N×N 형태의 연결 관계를 직접 확인하는 구조이다. 그래서 N이 한 번 더 곱해진 O(N^2)로 정리된다.

따라서 시간 복잡도는 O(N^2)이다.