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

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

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

BFS와 구현력을 요구하는 어렵지 않은 문제였다. 예전에 네이버에 이와 비슷한 문제가 나온적이 있어서 쉽게 풀었다. 간선을 하나씩 제거한 것을 기록하기 위해 2차원 배열을 이용했다. 그 후 BFS를 이용해 트리를 탐색하는데, 체크한 간선을 구성하고 있는 노드를 탐색하려고 하면 그대로 continue 해준다. 이런식으로 나눠진 트리의 노드 수를 각각 구하고, 이들의 차의 절댓값이 최소인 것을 찾으면 된다.

#include #include #include #include #include #include using namespace std; vector tree[101]; bool deleted[101][101]; bool visit[101]; int N, answer = INT_MAX; int BFS(int node) { queue q, u; q.push(node); u.push(node); visit[node] = true; while(!q.empty()) { int now = q.front(); q.pop(); for(int i = 0; i < tree[now].size(); i++) { int next = tree[now][i]; if(deleted[now][next] || deleted[next][now]) continue; if(!visit[next]) { q.push(next); u.push(next); visit[next] = true; } } } return u.size(); } int check() { int order = 1, first = 0, second = 0; for(int i = 1; i <= N; i++) { if(!visit[i]) { if(order == 1) first = BFS(i); else if(order == 2) second = BFS(i); order++; } } memset(visit, false, sizeof(visit)); return abs(first - second); } int solution(int n, vector> wires) { N = n; for(int i = 0; i < n - 1; i++) { tree[wires[i][0]].push_back(wires[i][1]); tree[wires[i][1]].push_back(wires[i][0]); } for(int i = 0; i < n - 1; i++) { int x = wires[i][0], y = wires[i][1]; deleted[x][y] = true; deleted[y][x] = true; answer = min(answer, check()); deleted[x][y] = false; deleted[y][x] = false; } return answer; }

반응형

from http://transferhwang.tistory.com/605 by ccl(A) rewrite - 2021-10-08 18:26:50