[C++]전력망을 둘로 나누기

요약

• 주어진 입출력 가공
• queue를 이용한 BFS 구현

풀이과정

1. 데이터 가공

추후 BFS를 편하게 구현하기 위해서 주어진 wires vector를 unordered_map<int,vector<int>> 형태로 변경하였다.

    unordered_map<int,vector<int>> mp;
    
    for(int i = 0; i < wires.size(); i++) {
        mp[wires[i][0]].push_back(wires[i][1]);
        mp[wires[i][1]].push_back(wires[i][0]);
    }

첫번째 문제의 경우 이렇게 값을 재구성했다. 

2. BFS 구현

이제 모든 wires의 element에 대해 BFS 탐색을 한다.

첫번째 테스트케이스를 예시로 들자면,

[4,7]을 끊었다 가정하였을 경우 첫번째 요소인 4와 연결된 노드를 BFS를 통해 파악할 것이다.

여기서 4와 7은 방문을 체크하는 vector에서 미리 true로 설정해주어 끊어짐을 설정한다.

BFS탐색은 queue를 통해 구현했다.

    for(int i = 0; i < wires.size(); i++) {
        //wires[i][0] --//-- wires[i][1]
        vector<bool> visit(n, false);
        visit[wires[i][0]] = true;
        visit[wires[i][1]] = true;
        int count = -1;
        queue<int> q;
        q.push(wires[i][0]);
        
        while(!q.empty()) {
            int x = q.front();
            count++;
            q.pop();
            for(int item : mp[x]) {
                if(visit[item] == false) {
                    q.push(item);
                    visit[item] = true;
                }
            }
        }
        ....

4--/--7 의 경우,

4 3567

3 124

5 4

6 4

이렇게 탐색하므로 4 3 5 6 1 2 가 나오고, 매번 count에 더해주게 되는데 count 값을 최초에 -1로 설정함으로서 자기자신을 자연스럽게 제외하게끔 하였다.

3. 값 도출

wires.size()는 총 연결의 개수이며, 끊어짐을 가정하므로 wires.size()-1이 전체 전력망의 개수가 된다.

여기서 count가 한 쪽의 연결이라면, wires.size()-1-count가 다른쪽의 연결이다.

서로 빼주면 2*count-wires.size()+1 이 나오게 되고, 음수가 나올 수 있으니까 abs로 절대값을 씌워준다.

        if(answer == -1 || abs(2*count-size+1) < answer)
            answer = abs(2*count-size+1);
        if(answer == 0)
            break;

answer가 -1이거나(첫 값), answer보다 작은 값이라면 answer를 갱신한다.

여기서 만약 answer가 0이라면 더이상 더 작은 값이 나올 수 없기 때문에 break하게 된다.

코드

#include <string>
#include <vector>

#include <iostream>
#include <unordered_map>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> wires) {
    int size = wires.size();
    int answer = -1;
    unordered_map<int,vector<int>> mp;
    
    for(int i = 0; i < wires.size(); i++) {
        mp[wires[i][0]].push_back(wires[i][1]);
        mp[wires[i][1]].push_back(wires[i][0]);
    }
    
    for(int i = 1; i <= n; i++) {
        cout << i << " ";
        for(int j = 0; j < mp[i].size(); j++)
            cout << mp[i][j];
        cout << endl;
    }
    
    for(int i = 0; i < wires.size(); i++) {
        //wires[i][0] --//-- wires[i][1]
        vector<bool> visit(n, false);
        visit[wires[i][0]] = true;
        visit[wires[i][1]] = true;
        int count = -1;
        queue<int> q;
        q.push(wires[i][0]);
        
        while(!q.empty()) {
            int x = q.front();
            count++;
            q.pop();
            for(int item : mp[x]) {
                if(visit[item] == false) {
                    q.push(item);
                    visit[item] = true;
                }
            }
        }
        if(answer == -1 || abs(2*count-size+1) < answer)
            answer = abs(2*count-size+1);
        if(answer == 0)
            break;
    }
    return answer;
}

다른 사람의 풀이

다음 공부 시간에 찾아보고 업데이트 예정.