알고리즘(C++) / 프로그래머스 위클리 챌린지 : 전력망을 둘로 나누기

위클리 챌린지(9주차) : 전력망을 둘로 나누기

https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 9주차

 

코드

//프로그래머스 전력망을 둘로 나누기
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> wires) {
    int answer = 1000001;
    //연결되어있는 노드 vec에 저장
    vector<vector<int>> vec(n + 1);
    for (int i = 0; i < wires.size(); i++) {
        vec[wires[i][0]].push_back(wires[i][1]);
        vec[wires[i][1]].push_back(wires[i][0]);
    }

    //wires 하나씩 끊어보기
    for (int i = 0; i < wires.size(); i++) {
        int size = 0;
        //연결된 것이 하나인 노드일 때
        if (vec[wires[i][0]].size() == 1 || vec[wires[i][1]].size() == 1) {
            size = n - 2;
        }
        else {
            //BFS 깊이 우선 탐색
            queue<int> q;
            q.push(wires[i][0]);
            size++;
            //방문 노드 확인
            bool visited[101] = { 0, };
            visited[wires[i][0]] = true;
            visited[wires[i][1]] = true;
            while (!q.empty()) {
                for (int j = 0; j < vec[q.front()].size(); j++) {
                    //방문하지 않은 노드
                    if (visited[vec[q.front()][j]] == false) {
                        q.push(vec[q.front()][j]); //연결되어있는 노드 push
                        visited[vec[q.front()][j]] = true; //방문
                        size++;
                    }
                }
                q.pop();
            }
            size = abs(size - (n - size)); //절댓값
        }
        answer = min(answer, size); //최솟값
    }

    return answer;
}

int main() {
    int n = 9;
    vector<vector<int>> wires = { {1,3}, {2,3}, {3,4}, {4,5}, {4,6}, {4,7}, {7,8}, {7,9} };
    cout << solution(n, wires) << "\n";
    return 0;
}

 

설명

• 2차원 벡터 vec에 연결되어 있는 노드를 저장한다.
• wires를 하나씩 끊어보면서 송전탑의 개수가 가능한 비슷하도록, 송전탑 개수의 차이가 가장 작을 때를 찾는다.
• 끊을 전선 중에서 한 노드가 연결되어있는 노드가 하나 뿐이라면 노드 하나와 나머지들로 나뉜다. 따라서 절댓값은 n-2를 가진다. (예로 1, 3이 끊어졌다면 1개 8개로 나뉘므로 송전탑 개수의 차이는 7개이다.)
• 연결된 노드가 여러개 일때는 BFS, 깊이 우선 탐색을 사용하여 연결되어있는 노드의 개수를 구한다.
• queue에 연결되어있는 노드중 방문하지 않은 노드만 push 해준다. 그렇게해서 연결되어 있는 노드의 개수를 구할 수 있다.
• 가장 작은 송전탑 개수의 차이를 구하고 return 할 수 있다. 

 

고찰

걸린시간 : 30분

코딩으로 먼저 접근하지 않고 일단 그냥 문제를 먼저 풀어봤다. 직관적인 방법을 배제하고 어떻게 구해야 답을 구할 수 있는지 생각하고 차근차근 문제를 해결하다보면 해결법이 난다. 

 

 

요즘 문제를 볼 때 해결법이 바로 생각나지 않으면 많이 답답하고.. 하기 싫어진다.. 집중해서 풀면 더 빨리 풀 수 있을거 같은데.. 집중력을 높이는 연습과 실전 환경과 같은 연습을 해야할 거 같다. 코딩테스트를 보면 보통 검색을 못하는 경우도 있고, IDE 사용이 안되는 경우가 많다... 그래서 프로그래머스 내에서 푸는 연습을 많이 해야할거 같다.