1. 전력망을 둘로 나누기
1) 문제
문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
제한 사항
n은 2 이상 100 이하인 자연수입니다.
wires는 길이가 n-1인 정수형 2차원 배열입니다.
wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
1 ≤ v1 < v2 ≤ n 입니다.
전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.입출력 예
n wires result
9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3
4 [[1,2],[2,3],[3,4]] 0
7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1
2) 문제 분석 및 풀이
1) 설계, 분석
DFS를사용한 완전탐색
2) 풀이
#include <string> #include <vector> #include <unordered_map> #include <unordered_set> #include <climits> #include <algorithm> using namespace std; vector<bool> visited; unordered_map<int, unordered_set<int>> adjList; int answer = INT_MAX; int dfs(int start) { int cnt = 1; if (visited[start]) return 0; visited[start] = true; for (auto& v : adjList[start]) { cnt += dfs(v); } return cnt; } int solution(int n, vector<vector<int>> wires) { // 그래프 정보 입력 for (auto& wire : wires) { adjList[wire[0]].insert(wire[1]); adjList[wire[1]].insert(wire[0]); } // 간선을 순회 for (auto& wire : wires) { // 해당 간선을 삭제 adjList[wire[0]].erase(wire[1]); adjList[wire[1]].erase(wire[0]); visited.clear(); visited.resize(n+1, false); // 삭제한 간선정보로 dfs 실행 int countA = dfs(1); // 간선 원상 복구 adjList[wire[0]].insert(wire[1]); adjList[wire[1]].insert(wire[0]); // 값 갱신 // countA == n 이면 2개로 나뉘어지지 않음. if (countA == n) continue; // 아닌경우 첫번째 구역의 노드가 A개 라면 남은 노드는 당연히 n-A; int countB = n - countA; // 최소값 갱신 answer = min(answer, abs(countA - countB)); } return answer; }
2. 가장 먼 노드
1) 문제
문제 설명
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한사항
노드의 개수 n은 2 이상 20,000 이하입니다.
간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.입출력 예
n vertex return
6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3
2) 문제 분석 및 풀이
1) 설계, 분석
BFS로 풀어도 되지만 다익스트라도 연습할 겸 2가지 방법으로 풀이
(다익스트라 사용함)
2) 풀이
#include <string> #include <vector> #include <queue> #include <climits> #include <unordered_map> using namespace std; unordered_map<int, vector<int>> adjList; vector<bool> visited; vector<int> cnt; int N; void BFS(int start) { visited.resize(N+1, false); queue<pair<int,int>> q; q.push({0, start}); visited[start] = true; cnt.push_back(0); while(!q.empty()) { auto [dist, node] = q.front(); q.pop(); if (dist > cnt.size() - 1) { cnt.push_back(1); } else { cnt[dist]++; } for(auto& to : adjList[node]) { if(visited[to]) continue; q.push({dist+1,to}); visited[to] = true; } } } int solution(int n, vector<vector<int>> edge) { int answer = 0; N=n; for (auto& e : edge) { adjList[e[0]].push_back(e[1]); adjList[e[1]].push_back(e[0]); } BFS(1); return answer = cnt[cnt.size()-1]; }
// 다익스트라 #include <string> #include <vector> #include <queue> #include <climits> #include <unordered_map> using namespace std; vector<vector<int>> dijkstraVec; unordered_map<int, vector<int>> adjList; vector<bool> visited; int N; void Dijkstra(int start) { dijkstraVec.resize(N+1, vector<int>(2,INT_MAX)); visited.resize(N+1, false); dijkstraVec[start][0] = 0; dijkstraVec[start][1] = start; // dist, node; queue<pair<int, int>> q; q.push({0,start}); while(!q.empty()) { auto [dist, currNode] = q.front(); q.pop(); if (visited[currNode]) continue; visited[currNode]= true; for (auto& v : adjList[currNode]) { int start2v = dijkstraVec[v][0]; int start2curr = dijkstraVec[currNode][0]; int curr2v = 1; if (start2v > start2curr + curr2v) { dijkstraVec[v][0] = start2curr + curr2v; dijkstraVec[v][1] = currNode; q.push({dijkstraVec[v][0], v}); } } } } int solution(int n, vector<vector<int>> edge) { int answer = 0; N=n; for (auto& e : edge) { adjList[e[0]].push_back(e[1]); adjList[e[1]].push_back(e[0]); } Dijkstra(1); int maxDist = 0; for (int i=1; i < N+1; i++) { maxDist = max(maxDist, dijkstraVec[i][0]); } for (int i=1; i < N+1; i++) { if (dijkstraVec[i][0] == maxDist) answer++; } return answer; }
