[알고리즘] 창용 마을 무리의 개수

 

0. 문제

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

---

1. 문제 이해

이건 인접리스트를 만들고 dfs로 connected component의 수를 세는 문제라고 생각했다.

---

2. 실패

가. 실패 : 입력값 범위

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAX_N = 100;
int n, m, visited[MAX_N];
vector<int> adj[MAX_N];

void dfs(int node){
    visited[node]++;

    for(int next : adj[node]){
        if(visited[next]) continue;
        dfs(next);
    }

    return;
}

int solve(){
    int cnt = 0;

    for(int i = 0; i < n; i++){
        if(visited[i]) continue;
        dfs(i);
        cnt++;
    }

    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;

    for(int tc = 1; tc <= T; tc++){
        fill(&visited[0], &visited[0] + MAX_N, 0);
        for(vector<int> vec : adj)
            vec.clear();
        cin >> n >> m;

        int tmp1, tmp2;
        for(int i = 0; i<m; i++){
            cin >> tmp1 >> tmp2;
            adj[tmp1].push_back(tmp2);
            adj[tmp2].push_back(tmp1);
        }

        int ret = solve();

        cout << "#" << tc << " " << ret << '\n';
    }
    return 0;
}
Code language: PHP (php)

입력값(사람의 번호)의 범위가 1부터 시작한다.

int tmp1, tmp2;
for(int i = 0; i<m; i++){
    cin >> tmp1 >> tmp2;
    adj[tmp1-1].push_back(tmp2-1);
    adj[tmp2-1].push_back(tmp1-1);
}
Code language: HTML, XML (xml)

위와 같이 -1한다.

---

나. for(vector vec : adj)의 vec는 read-only index입니다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAX_N = 100;
int n, m, visited[MAX_N];
vector<int> adj[MAX_N];

void dfs(int node){
    visited[node]++;

    for(int next : adj[node]){
        if(visited[next]) continue;
        dfs(next);
    }

    return;
}

int solve(){
    int cnt = 0;

    for(int i = 0; i < n; i++){
        if(visited[i]) continue;
        dfs(i);
        cnt++;
    }

    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;

    for(int tc = 1; tc <= T; tc++){
        fill(&visited[0], &visited[0] + MAX_N, 0);
        for(vector<int> vec : adj)
            vec.clear();
        cin >> n >> m;

        int tmp1, tmp2;
        for(int i = 0; i<m; i++){
            cin >> tmp1 >> tmp2;
            adj[tmp1-1].push_back(tmp2-1);
            adj[tmp2-1].push_back(tmp1-1);
        }

        int ret = solve();

        cout << "#" << tc << " " << ret << '\n';
    }
    return 0;
}
Code language: PHP (php)

for(vector<int> vec : adj)은 제대로 초기화되지 않는다!

C++에서 vector는 call by value다.

기존의 벡터를 복사한 새로운 벡터를 비우는 것이므로 실제 adj 배열의 벡터를 비우지 않는다.

이 문제는 “for-each loop” 또는 “enhanced for loop”에서 발생한다.

각 요소를 반복적으로 접근하기에 간편하지만 해당 요소를 변경하여 원본 자체를 수정할 수는 없다.

이러한 점에서 vec와 같아 수정할 순 없는 요소를 “read-only index” 또는 “읽기 전용 인덱스” 라고 부르기도 한다.

+ 배열은 call by reference이다. for-each문에서 복사한 값이 주소값이기 때문에 문제없이 원본에 접근할 수 있다.

---

3. 성공

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAX_N = 100;
int n, m, visited[MAX_N];
vector<int> adj[MAX_N];

void dfs(int node){
    visited[node]++;

    for(int next : adj[node]){
        if(visited[next]) continue;
        dfs(next);
    }

    return;
}

int solve(){
    int cnt = 0;

    for(int i = 0; i < n; i++){
        if(visited[i]) continue;
        dfs(i);
        cnt++;
    }

    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;

    for(int tc = 1; tc <= T; tc++){
        fill(&visited[0], &visited[0] + MAX_N, 0);
        for(vector<int>& vec : adj)
            vec.clear();
        cin >> n >> m;

        int tmp1, tmp2;
        for(int i = 0; i<m; i++){
            cin >> tmp1 >> tmp2;
            adj[tmp1-1].push_back(tmp2-1);
            adj[tmp2-1].push_back(tmp1-1);
        }

        int ret = solve();

        cout << "#" << tc << " " << ret << '\n';
    }
    return 0;
}
Code language: PHP (php)

for(vector<int>& vec: adj)로 고치거나…

for(int i = 0; i < MAX_N; ++i) {
    visited[i] = 0;
    adj[i].clear();
}
Code language: HTML, XML (xml)

위와 같이 초기화해야 한다.

---