프로그래머스 네트워크

문제

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

코드

cpp

#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(computers[i][j]==1){
                answer++;
                computers[i][j]=0;
                queue<pair<int,int>> q;
                q.push({i,j});
                while(!q.empty()){
                    int y=q.front().first;
                    int x=q.front().second;
   
                    q.pop();
                    
                    for(int k=0;k<n;k++){
                        if(k!=y&&computers[k][x]==1){
                            computers[k][x]=0;
                            q.push({k,x});
                        }
                    }
                    for(int k=0;k<n;k++){
                        if(k!=x&&computers[y][k]==1){
                            computers[y][k]=0;
                            q.push({y,k});
                        }
                    }                    
                }
            }
        }
    }
    return answer;
}

python

visit=[0]*200

def dfs(node,computers,n):
    visit[node]=1
    for i in range(n):
        if i==node or visit[i] or computers[node][i]==0:
            continue
        dfs(i,computers,n)
        
def solution(n, computers):
    answer = 0
    for i in range(n):
        if visit[i]:continue
        answer+=1
        dfs(i,computers,n)
        
    return answer

풀이

문제 보시면 2차원 배열을 사용해서 그래프를 표현했고 i번째 노드와 j번째 노드사이의 간선은 graph[i][j],graph[j][i]에 1을 넣어서 표현했습니다.

연결된 노드들은 한개의 네트워크고 총 몇개의 네트워크가 있는지 구하는 문제입니다.

dfs bfs 아무거나 사용해도 되는데 저는 cpp는 bfs를 사용했습니다. dfs는 pyhton으로 풀었습니다.