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

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

728x90

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

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

코드

//프로그래머스 전력망을 둘로 나누기 #include #include #include #include #include using namespace std; int solution(int n, vector> wires) { int answer = 1000001; //연결되어있는 노드 vec에 저장 vector> 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 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> wires = { {1,3}, {2,3}, {3,4}, {4,5}, {4,6}, {4,7}, {7,8}, {7,9} }; cout << solution(n, wires) << "

"; return 0; }

설명

2차원 벡터 vec에 연결되어 있는 노드를 저장한다.

wires를 하나씩 끊어보면서 송전탑의 개수가 가능한 비슷하도록, 송전탑 개수의 차이가 가장 작을 때를 찾는다.

끊을 전선 중에서 한 노드가 연결되어있는 노드가 하나 뿐이라면 노드 하나와 나머지들로 나뉜다. 따라서 절댓값은 n-2를 가진다. (예로 1, 3이 끊어졌다면 1개 8개로 나뉘므로 송전탑 개수의 차이는 7개이다.)

연결된 노드가 여러개 일때는 BFS, 깊이 우선 탐색을 사용하여 연결되어있는 노드의 개수를 구한다.

queue에 연결되어있는 노드중 방문하지 않은 노드만 push 해준다. 그렇게해서 연결되어 있는 노드의 개수를 구할 수 있다.

가장 작은 송전탑 개수의 차이를 구하고 return 할 수 있다.

고찰

걸린시간 : 30분

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

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

728x90

from http://se-jung-h.tistory.com/176 by ccl(A) rewrite - 2021-10-06 11:00:45