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

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

728x90

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

문제 풀이

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

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

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

느낀 점

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

코드

#include #include #include #include #include #include using namespace std; set s[101]; int BFS(int node, vector>& wires) { int length = 0; queue 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> 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; }

반응형

from http://codinghejow.tistory.com/131 by ccl(A) rewrite - 2021-10-10 02:00:57