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

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

예전에 풀었다가 파이썬으로 다시 도전한 문제.

JS

function solution(n, computers) {
    let answer = 0;  // 네트워크 개수를 저장하는 변수 초기화
    let visit = [...computers];  // 컴퓨터 방문 여부를 나타내는 배열을 생성하고 computers 배열 복사
  
    for (let i = 0; i < n; i++) {  // 모든 컴퓨터에 대한 반복문 시작
      if (visit[i][i] !== -1) {  // 아직 방문하지 않은 컴퓨터인 경우
        answer++;  // 새로운 네트워크를 시작하고 answer 증가
        visit[i][i] = -1;  // 방문 표시 (-1로 표시하여 중복 방문을 막음)
      }
  
      dfs(i, visit, computers, n);  // DFS 함수 호출하여 연결된 모든 컴퓨터 탐색
      
    }
  
    
      
  function dfs(i, visit, computers, n) {  // 깊이 우선 탐색 함수 정의
    for (let j = 0; j < n; j++) {  // 현재 컴퓨터와 연결된 모든 컴퓨터에 대한 반복문 시작
      if (visit[i][j] !== -1 && computers[i][j] === 1) {  // 아직 방문하지 않았고 연결되어 있는 경우
        visit[i][j] = -1;  // 방문 표시 (-1로 표시하여 중복 방문을 막음)
        visit[j][i] = -1;  // 양방향 연결을 고려하여 반대 방향도 방문 표시
        dfs(j, visit, computers, n);  // DFS 함수 호출하여 연결된 모든 컴퓨터 탐색
      }
    }
  }
    
  
    return answer;  // 최종적으로 찾은 네트워크 개수 반환
  }

모든 컴퓨터에 대해서 방문을 시작하는데 방문은 DFS로 했다. 그래서 DFS 돌면서 visited에 표시를 해줘서 다음번에 같은 컴퓨터 방문 안하게 막아줬다. 그래서 몇 번 방문을 시작했는지 세서 답을 구했다.

Python

def find(x, parent):
  if x != parent[x]:
    parent[x] = find(parent[x], parent)
  return parent[x]

def union(a, b, parent):
  pa = find(a, parent)
  pb = find(b, parent)
  
  parent[pb] = pa

def solution(n, computers):
    answer = 0
    
    edges = []
    
    for i in range(n):
      for j in range(i+1, n):
        if computers[i][j] == 1:
          edges.append((i, j))
    
    parent = [i for i in range(n)]
    for e in edges:
      i, j = e
      if find(i, parent) != find(j, parent):
        union(i, j, parent)
        
    for i in range(n):
      parent[i] = find(i, parent)
      
    answer = set(parent)
    
    return len(answer)

파이썬으로는 union-find를 활용했다. 인접행렬로 되어 있는 네트워크를 대각선 위쪽 원소만 돌면서 edge로 바꿨다.
그러고 edge를 돌면서 union-find를 진행했고, 맨 마지막에 find함수를 한 번 더 돌면서 parent 배열의 원소를 각각의 root로 통일시켰다.
마지막으로 parent배열에 root가 몇 개 있는지 구함으로써 답을 구했다.