[C++] 프로그래머스 : 위클리 챌린지 (9주차)

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

코딩테스트 연습 - 9주차

---

 문제 풀이

노드의 최대 개수가 100개이므로 전부 탐색을 하면서 간선의 길이를 구해서 따지면 된다.

BFS를 통해서 간선의 최대 길이를 따지고

STL::set을 이용해서 각 노드마다 연결된 노드를 저장해준다.

 느낀 점

처음에는 전혀 접근하 지를 못해서 조금의 구글링으로 도움을 받았다. 그래프 관련된 문제를 좀 더 많이 풀어봐야 할 것 같다.

 코드

#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

set<int> s[101];

int BFS(int node, vector<vector<int>>& wires) {
    int length = 0;
    queue<int> q;
    q.push(node);

    bool visited[101] = { false, };
    visited[node] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        length++;

        for (auto next : s[cur]) {
            if (visited[next]) continue;
            q.push(next);
            visited[next] = true;
        }
    }
    return length;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 100;

    for (auto wire : wires) {
        s[wire[0]].insert(wire[1]);
        s[wire[1]].insert(wire[0]);
    }

    for (auto wire : wires) {
        s[wire[0]].erase(wire[1]);
        s[wire[1]].erase(wire[0]);

        answer = min(answer, abs(BFS(wire[0], wires) - BFS(wire[1], wires)));

        s[wire[0]].insert(wire[1]);
        s[wire[1]].insert(wire[0]);
    }

    return answer;
}