M'S Blog

M'S Blog

WWDC20 student challenge Winner!

프로그래머스 - 네트워크

최대 1 분 소요

문제

프로그래머스 - 네트워크 풀러가기

문제 분석

이 문제는 연결 요소를 찾는 문제입니다.

연결 요소 보러가기

이 개념만 안다면 쉽게 푸실 수 있는 문제에요!

문제 코드(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <string>
    #include <vector>
    #include <queue>
     
    using namespace std;
     
    int solution(int n, vector<vector<int>> computers) {
        int answer = 0;
     
        vector<bool> visit(n, false);
     
        for(int i=0;i<n;i++){
            if(!visit[i]){
                visit[i] = true;
                queue<int> q;
                q.push(i);   
                while(!q.empty()){
                    int cur = q.front();
                    q.pop();
                    for(int k=0;k<n;k++){
                        if(!visit[k] && computers[cur][k] == 1){
                            q.push(k);
                            visit[k] = true;
                        }
                    }
                }
                answer++;
            }
        }
     
        return answer;
    }
    		cs
    • 13번째 줄 : 아직 탐색이 안 되었다 = 새로운 연결 요소의 시작
      • 이를 지점을 시작으로 해서 새로운 탐색을 시작하면 됩니다.
      • 15~26번째 줄 : bfs 구현 부분





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고