[ 프로그래머스 C++ ] 네트워크 - BFS로 해결

문제 

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

프로그래머스

 

bfs() 함수 코드 

0번째 컴퓨터와 연결된 컴퓨터들을 큐에 넣는다. 
큐 [ (0) ]

1번 컴퓨터와 연결된 컴퓨터를 큐에 넣는다.(방문하지 않는 컴터만) 
큐 [ (1) ] 

2번 컴퓨터와 연결된 컴퓨터를큐에 넣는다. 
.
.
.
.
더이상 연결된 컴퓨터가 없을 때 answer++한다. 

메인함수 ()

컴퓨터의 개수 만큼 반복 
방문하지 않은 컴퓨터가 있다면 
bfs() 
없다면 반복문 끝 

return answer

 

코드 

#include <string>
#include <vector>
#include <queue>
using namespace std;
queue<int> q;

int visited[200]={0,};//방문여부 확인 0이면 X, 1이면 방문
vector<vector<int>> maps; //a<->b 연결
int cnt=0;

void bfs(int point,vector<vector<int>> computers) //point에서 부터 주변살피기
{
    q.push(point);
    while(!q.empty())
    {
        int now = q.front();
        visited[now]=1;
        q.pop();
        for(int i=0; i<computers.size(); i++)
        {
            if(computers[now][i]==1 && visited[i]==0)
            {
                q.push(i);
            }
        }
        
    }
    cnt ++;
}

int solution(int n, vector<vector<int>> computers) {
    
    for(int i=0; i<n; i++)
    {
        if(visited[i]==0)
        {
            bfs(i,computers);
        }
    }
    return cnt;
}

 

처음에 visited를 vector<int>visited;이렇게 했다가 몇몇개에서 오류가 났다. (코드 실행 눌렀을 때는 문제 없었음)  

그래서 int[최대] visited = {0,}으로 변경했다. 처음부터 크기를 정해주는게 좋지싶다. 

깊이우선 탐색으로 풀 수 도 있지만 난 BFS가 편한것같다.

~끗~