풀이 방법 이 문제는 트리에서 dp를 이용하는 문제이다. dp[현재 노드][현재 노드가 얼리어답터인가 여부]로 dp테이블을 만들고 현재 노드가 얼리어답터가 아니라면 자식노드는 항상 얼리어답터이고, 얼리어답터라면 얼리어답터일수도, 아닐수도 있다. 이 문제는 이 문제 와 매우 비슷하여 쉽게 해결하였다. 코드 #include using namespace std; vector v, tree; int dp[1000006][2]; bool visited[1000006]; //단방향 그래프로 바꾼다 void dfs(int cur) { if (visited[cur]) return; visited[cur] = true; for (auto nxt : v[cur]) { if (!visited[nxt]) { tree[cur]..

풀이 방법 이 문제는 트리에서의 dp문제 이다. 저는 맞왜틀을 외치다 여기 를 참고했습니다. 우선 dfs를 이용하여 임의의 루트를 정하여 그 트리의 경로를 저장합니다. dp정의는 dp[현재 노드][현재 노드를 포함하는가 여부]로 정의하고, 만약 현재 노드를 포함한다면 자식 노드는 포함 할 수 없고, 포함하지 않는다면 자식노드를 포함하든 안하든 상관이 없다. 포함하는 경로 추적은 루트 노드부터 시작해서 dfs를 돌며 dpf를 돌때 저장한 배열의 값이 true인 경우를 ans배열에 저장한다. 코드 #include #include #include using namespace std; int cost[10004], dp[10004][2], check[10004], res; vector v, tree; vecto..

풀이 방법 크루스칼 알고리즘을 이용하여 풀이한다. 이미 연결 된 간선은 미리 연결해놓고 가장 거리가 짧은 간선을 뽑아 사이클이 있는지 확인하고 연결한다. 코드 우선순위큐를 이용한 구현 #include #include #include #include #include using namespace std; using ll = long long; using pll = pair; using pdll = pair; pll arr[1003]; ll N, M, par[1003], cnt, lev[1003]; priority_queue pq; ll dist(pll a, pll b) { return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (..