[백준/C++] 알고리즘 2617번 - 구슬 찾기

 

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 2617번 - 구슬 찾기 를 풀어보도록 하겠습니다.

 

[문제 접근]

문제에서 답에 포함되는 상황은 특정 구슬이 (n+1)/ 2개보다 더 무겁거나 같은 구슬의 개수를 가지거나, 더 가볍거나 같은 구슬의 개수를 가지는 상황입니다. 그래서 저는 특정구슬보다 무거운 구슬들을 담는 공간과 특정구슬보다 가벼운 구슬 공간을 담기 위해 인접리스트 두 개를 이용했습니다. 특정 구슬의 인접리스트 원소 그리고 인접리스트 원소가 연결된 모든 원소들이 몇개인지 파악하기 위해 BFS를 생각했습니다.

 

[풀이 전략]

1. 인접리스트를 이용하여 구슬 간의 관계를 저장합니다.

2. 모든 구슬을 for문을 이용하여 방문합니다.

- for문의 한 턴이 시작될 때마다 방문 구슬을 저장하는 배열을 초기화합니다.

- BFS를 이용하기 위해 queue와 방문배열을 이용합니다.

- cnt 변수를 생성하여 구슬과 연결된(직접 혹은 간접) 구슬의 개수를 셉니다.

- cnt >= (n+1)/2 이면 정답에 포함시킵니다.

 

[코드]

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int m , n; 

vector<int> adj1[100];
vector<int> adj2[100];
int vis[100];
queue<int> q ; 

int result ;

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n >> m ; 
    while(m--) {
      int a, b ;
      cin >> a >> b ; 
      adj1[a].push_back(b);
      adj2[b].push_back(a);
    }

    for(int i = 1 ; i <=n ; i++){
      fill(vis,vis+100,0);
      q.push(i);
      vis[i] = 1 ;

      int cnt = 0 ;
      while (!q.empty())
      {
        auto cur = q.front() ; q.pop();
          for(auto nxt : adj1[cur]){
            if(vis[nxt]) continue;
            q.push(nxt);
            vis[nxt] = 1;
            cnt++;
          }
      }
      if(cnt >= (n+1)/2) {result++; continue;}
      }
    
      
      for(int i = 1 ; i <=n ; i++){
      fill(vis,vis+100,0);
       q.push(i);
      vis[i] = 1 ;

      int cnt = 0 ;
      while (!q.empty())
      {
        auto cur = q.front() ; q.pop();
          for(auto nxt : adj2[cur]){
            if(vis[nxt]) continue;
            q.push(nxt);
            vis[nxt] = 1;
            cnt++;
          }
      }
      if(cnt >= (n+1)/2) result++;
    }
    cout << result ; 
}

 

[배울 점]

- 공간복잡도도 고려해야 합니다.

- 반복성이 보이면 함수를 만드는 것이 효율적입니다.

- 방문여부 등의 저장배열의 초기화 타이밍을 신경써주어야 합니다.

- BFS의 기본 뼈대를 상기시켜야 합니다.