프로그래머스 43162 - 네트워크 (c++)

프로그래머스 43162 - 네트워크

문제 링크

접근 및 생각

사족

• 프로그래머스의 대부분 풀이들은 DFS 방식이였지만, 내가 이 문제를 처음 접근할 때 BFS 방식이 먼저 떠올라서 BFS 방식으로 풀게 되었다.

본론

• BFS에 관한 내용은 (링크)를 참조
• BFS는 큐를 활용하는 탐색 방식으로, 코드로 구현할 때 다음과 같은 요소를 고려하여야 한다.
  • queue의 데이터 타입
  • queue의 초깃값
  • q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동
  • 읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

queue의 데이터 타입

• queue가 기억해야 할 것은 computers의 index 값이므로 queue<int> q;

queue의 초깃값

• 일단 computers의 0번 index부터 탐색할 것이므로 q.push(0); visit[0] = answer;
• 그리고 computers의 index를 탐색했는 지 기억하기 위해 int visit[200]; 선언

읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

• computers[q.front()][i = 0..n] 을 탐색해서,
  • q.front()와 연결되어 있고, (computers[i][temp] == 1)
  • 아직 방문하지 않았다면, (visit[i] == 0)
    q.push();

q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동

• 정보 update가 가능한 시점
  • 더이상 탐색할 수 있는 원소가 없는 경우 한 네트워크를 다 찾은 것이므로, (if(q.empty()))
  • 다른 네트워크를 찾아야 한다.

      for(int i = 0; i < n; i++){
          if(visit[i] == 0){
              q.push(i);
              visit[i] = ++answer;
              break;
          }
      }

  • 위 과정을 거쳐도 추가된 원소가 없다면 (즉, 모든 컴퓨터를 탐색했다면) , return answer

코드

#include <bits/stdc++.h>
using namespace std;

queue<int> q;
int visit[200], answer = 1;

int solution(int n, vector<vector<int>> computers) {    
    q.push(0);
    visit[0] = answer;
    while(-1){
        if(q.empty()){
            for(int i = 0; i < n; i++){
                if(visit[i] == 0){
                    q.push(i);
                    visit[i] = ++answer;
                    break;
                }
            }
            if(q.empty())   return answer;
        }

        int temp = q.front();
        q.pop();

        for(int i = 0; i < n; i++){
            if(i == temp) continue;
            else if(computers[i][temp] == 1 && visit[i] == 0){
                q.push(i);
                visit[i] = answer;
            }
        }
    }
}

채점 결과