프로그래머스-네트워크

문제 링크

1. 문제 접근 과정🧐

1. 연결된 컴퓨터를 그래프로 초기화
2. 연결된 컴퓨터에서 방문하지 않은 컴퓨터를 BFS(혹은 DFS)
3. BFS(혹은 DFS) 한 횟수가 정답
   
   

2. 시행착오🤯

• 시행착오를 크게 겪은 것은 없지만 신경써야 할 부분이 있다.
  • 컴퓨터를 1부터 n까지로 초기화 했기에 이를 고려해야 한다.
  • 자기 자신으로 향하는 네트워크는 고려하지 않아도 된다.
    
    

3. 개선한 코드😄

• 위의 고려해야 할 부분을 생각하여 BFS로 해결
  

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<int> graph[n + 1];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i != j && computers[i][j]){
                graph[i + 1].push_back(j + 1);
            }
        }
    }
    vector<bool> visited(n + 1, false);
    for(int i = 1; i <= n; i++){
        if(!visited[i]){
            answer++;
            queue<int> q;
            visited[i] = true;
            q.push(i);
            while(!q.empty()){
                int cur = q.front();
                q.pop();
                for(int n : graph[cur]){
                    if(!visited[n]){
                        visited[n] = true;
                        q.push(n);
                    }
                }
            }
        }
    }
    return answer;
}

4. 회고💭

• DFS로 푸는 방법도 다음에 해봐야겠다.
• 인덱스가 0-based, 1-based 중 어느 것으로 하였는지 잘 생각하고 풀어야 한다.