반응형
문제 : https://programmers.co.kr/learn/courses/30/lessons/43162
서론
문제를 보고 연결된 네트워크 따라 탐색시키면 되겠다 생각하고 코드를 완성한 후 분류를 봤더니 DFS/BFS문제다. 그리고 다시 내 코드를 봤더니 BFS였다.
BFS는 생각하지도 않았는데 자연스럽게 BFS로 풀이된게 뿌듯하다. 조금은 체화된것같다.
풀이
DFS/BFS문제
answer를 1 증가시키면서 1번 노드에 방문하면 방문표시를 한다. 그리고 방문한 노드와 연결된 노드가 있고 아직 방문을 안했으면 방문하고 방문표시를 한다. 더이상 연결된 노드가 없을때까지 탐색하면 하나의 네트워크를 만들 수 있다.
그리고 위의 과정 전체를 아직 방문하지 않은 노드가 남아있을 때까지 반복한다.
구현
// c++
#include <string>
#include <vector>
#include <queue>
using namespace std;
int node[201];
int solution(int n, vector<vector<int>> computers) {
int answer = 0;
queue<int>q;
for(int i=0, size = computers.size(); i<size; i++){
if(node[i] == 1) continue;
q.push(i);
while(!q.empty()){
int cur = q.front();
q.pop();
for(int j=0; j<size;j ++){
if(computers[cur][j] == 1 && node[j] == 0) {
node[j] = 1;
q.push(j);
}
}
}
answer++;
}
return answer;
}
최근댓글