[파이썬, Java] 네트워크

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

 

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

 

 

 

 

🍔 나의 풀이

 

def solution(n, computers):
    answer = 0
    visited = [0] * n
    for i in range(n):
        if visited[i] == 0:
            dfs(visited, computers, n, i)
            answer += 1
    return answer

def dfs(visited, computers, n, i):
    for j in range(n) :
        # 방문한 적 없고 연결되어 있으면
        if visited[j] == 0 and computers[i][j] == 1:
            visited[j] = 1  # 방문 처리
            dfs(visited, computers, n, j)

 

visited[i]가 방문한 적 없다면(==0) dfs함수 호출.

visited와 computers는 solution 함수 내의 지역 변수이므로 visited와 computers도 인자로 넘김.

연결된 컴퓨터가 있다면 방문 처리 된다.(visited[j]=1)

재귀 호출이 되었으면 방문했기 때문에 solution에서 dfs를 호출하는 횟수가 그만큼 줄어든다.

따라서 answer+=1은 네트워크의 개수를 나타냄.

 

from collections import deque

def solution(n, computers) :
  answer=0
  visited=[False for i in range(n)]
  for com in range(n) :
    if visited[com] == False :
      BFS(n, computers, com, visited)
      answer+=1
  return answer

def BFS(n, computers, com, visited) :
  visited[com]=True
  queue=deque()   # 큐 생성
  queue.append(com)   # 시작점 
  while queue :
    com=queue.popleft()
    visited[com]=True
    for connect in range(n):
      if connect != com and computers[com][connect] == 1 :
        if visited[connect] == False :
          queue.append(connect)

 

BFS 구현.

위랑 알고리즘은 같음.

 

from collections import deque

def solution(n, computers):
    visited = [0] * n

    def bfs(com):
        que = deque([com])
        flag = 0
        while que:
            v = que.popleft()
            visited[v] = 1
            for idx, c in enumerate(computers[v]):
                if not visited[idx] and c == 1 :
                    que.append(idx)
                    flag = 1
        return True if flag else False

    cnt=0
    for com in range(n):
        if not visited[com] :
            visited[com] = 1
            if bfs(com):
                cnt += 1  # 네트워크 개수
            else :
                cnt+=1
    return cnt

 

BFS 구현

연결된 컴퓨터가 있으면 flag를 1로 변환한다. 

연결되지 않은 컴퓨터만(visited가 0인 것) bfs를 호출

bfs 호출 전에 자기 자신은 방문 처리해줬다.

 

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited=new boolean[n];

        for(int i=0; i<n; i++){
            if (visited[i] == false){
                bfs(computers, i);
                answer++;
            }
        }
        return answer;
    }

    boolean[] visited;
    int node=0;
    public void bfs(int[][] computers, int i){
        Queue<Integer> que=new LinkedList<>();
        que.offer(i);
        while (!que.isEmpty()) {
            node=que.poll();
            visited[node]=true;
            for(int j=0; j<computers.length; j++){
                if (computers[node][j]==1 && visited[j] == false){
                    que.offer(j);
                }
            }
        }
    }
}

 

bfs로 구현

 

 

🍖 다른 사람 풀이

 

def solution(n, computers) :
  answer=0
  visited=[0 for i in range(n)]
  def dfs(computers, visited, start) :
    stack=[start]
    while stack :
      j=stack.pop()
      if visited[j] == 0 :  # 방문한 적 없음
        visited[j]=1
      for i in range(0, len(computers)) :
        if computers[j][i] == 1 and visited[i] == 0 :
          stack.append(i)
  i=0
  while 0 in visited :
    if visited[i] == 0 :
      dfs(computers, visited, i)
      answer+=1
    i+=1
  return answer

 

스택으로 구현한 dfs 풀이.

 

# 출처 : https://velog.io/@timointhebush/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-DFS-BFS-Python
def solution(n, computers) :
  answer=0
  visited=[False for i in range(n)]
  for com in range(n) :
    if visited[com] == False :
      BFS(n, computers, com, visited)
      answer+=1
  return answer

def BFS(n, computers, com, visited) :
  visited[com]=True
  queue=[]
  queue.append(com)
  while len(queue) != 0 :
    com=queue.pop(0)
    visited[com]=True
    for connect in range(n):
      if connect != com and computers[com][connect] == 1 :
        if visited[connect] == False :
          queue.append(connect)

 

BFS로 구현한 풀이.

deque를 썼다면 좋았을 텐데..

이건 그냥 스택이다.

 

 

// https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java
import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] check=new boolean[n];
        
        for(int i=0; i<n; i++){
            if(!check[i]){
                dfs(computers, i, check);
                answer++;
            }
        }
        return answer;
    }
    
    boolean[] dfs(int[][] computers, int i, boolean[] check){
        check[i]=true;
        
        for(int j=0; j<computers.length; j++){
            if(i != j && computers[i][j] == 1 && check[j] == false){
                check=dfs(computers, j, check);
            }
        }
        return check;
    }
}

 

재귀를 이용한 dfs

 

 

 

 

 

문제 출처 👉 프로그래머스