코딩 공부 연습
프로그래머스 - 네트워크
miffy짱
2022. 8. 24. 16:16
반응형
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
queue <int> q;
int visited[202] = {0,};
int solution(int n, vector<vector<int>> computers) {
int answer = 0;
// 처음부터 시작해서, 1인 애들을 전부다 큐에 넣었다가 팝해주면서 시작점에서 이어진 애들 전부 다 체크, visited 해놓기
// visited 안 된 점을 또 큐에 푸시하고 같은 동작반복
// for문을 컴퓨터 사이즈 만큼 돌리고, 그안에서 dfs 반복하면 될거같음.
int cnt = 0;
for(int i = 0; i< computers.size(); i++)
{ // 컴퓨터 개수만큼 for문 돌면서
if (visited[i] == 0) //방문안한 점일 때는 그 점을 푸쉬하고 거기서부터 이어진 간선을 전부 dfs 로 찾아냄.
{
q.push(i);
while (!q.empty())
{
int cur = q.front();
q.pop();
for (int j = 0; j < computers.size(); j++)
{
if (computers[cur][j] == 1 && visited[j] == 0)
{
q.push(j);
visited[j] = 1;
}
}
}
cnt++;
}
}
return cnt;
}
이번에는 dfs 를 다시 공부한 김에 프로그래머스에서 dfs 유형을 한번 풀어보았당! 초반에 dfs를 어떻게 사용할 지 좀 고민했었는데 생각해보니 완전 정석적인 친구였다. 풀려서 다행이다. 우선 첫번째 점부터 큐에 넣고, 그 점에 연결된 점들을 전부 다 dfs 로 찾았다. 이 dfs는 이전에 했던 방식이랑 거의 다르지 않다ㅎ
이후 for문으로 2,3번째 점들을 다 확인하는데, 이미 방문한 점이면 걍 넘어갔다.
숙취때문에 2시까지 뻗어있었는데 기분이좋다!