본문 바로가기

전체 글

BOJ)10216 Count Circle Groups 문제: icpc.me/10216 N개의 진영이 주어 질 때 각 진영이 통신영역이 닿거나 겹치는 부분이 있으면 서로 통신이 가능하다. 그리고 직접적으로 통신이 불가능 하더라도 중간에 몇개의 통신을 거쳐서 통신이 가능하다면 i와 j는 통신이 가능하다고 본다. 통신이 서로 가능한 진영들을 그룹으로 묶을 때 그룹의 수를 출력하는 문제이다. 우리는 a와b가 통신이 가능하고 b와c가 통신이 가능하면 a와c가 통신이 가능한 그룹이 된다는 사실을 가지고 disjoint set을 통하여 문제를 해결할 수 있다. N이 3000밖에 되지 않으므로 N^2의 방법으로 각 진영들을 비교하여 같은 그룹이 아닌 그룹들중에서 통신영역이 겹치는 두 그룹을 union 시켜주면서 시켜줄때마다 그룹의 수를 하나씩 차감시키는 방법으로 답을 구.. 더보기
BOJ)13913 숨바꼭질4 문제:icpc.me/13913 X의 위치에서 1초후에 X+1,X-1,2*X의 위치로 이동가능할 때 K로 가는데 걸리는 가장 빠른시간과 경로를 출력하는 문제이다. 우리는 각 좌표를 정점으로 생각하여 다익스트라를 돌린다면 가장 빠른시간을 구할 수 있다. 경로를 출력하는것은 백트래킹을 해야하는데 좌표N에 대한 최단경로가 갱신되는 순간에 N을 부른 위치를 기록해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include using namespace std;int dp[250000], n, k, back[250000];stack st;int main().. 더보기
BOJ)13549 숨바꼭질3 문제:icpc.me/13549 X의 위치에서 1초후에 X+1혹은 X-1로 이동가능하고 순간이동을 할경우 0초후에 2*X위치로 이동가능할 때 K까지 가는 가장 빠른 시간을 출력하는 문제이다. 각 좌표를 정점으로 생각하여 다익스트라를 돌리면 된다. 12345678910111213141516171819202122232425262728#include #include #include #include using namespace std;int dp[250000], n, k;int main() { scanf("%d%d", &n, &k); memset(dp, -1, sizeof(dp)); priority_queue pq; pq.push({ 0, n }); while (pq.size()) { int here = pq.t.. 더보기

티스토리툴바