프로그래머스 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;
            }
        }
    }
}

채점 결과

+ Recent posts