본문 바로가기

백준34

BOJ 12012 - Closing the farm (유니온파인드) https://www.acmicpc.net/problem/12012 거꾸로 생각해서 쉬워지는 문제 최대 2e5개의 정점과 간선으로 이뤄진 양방향 그래프가 주어진다. 정점의 개수를 n이라고 할때 쿼리가 n개 들어온다. 각 쿼리에선 정점이 하나 주어지는데(u), 현재 전체 컴포넌트의 수가 1이라면 YES를, 1이상이라면 NO를 출력한 후, 해당 정점과 정점에 연결된 간선을 모두 지운다. 문제 설명대로 완성된 그래프에 간선을 지워가면서 컴포넌트의 수를 log시간 이하로 구하는 것은 매우 어렵다. (불가능한 것 같다) 쿼리를 기록해두고 거꾸로 접근하면, 아무것도 없는 그래프에 정점과 연결된 컴포넌트를 이어주며 컴포넌트의 개수를 유지하는 문제로 바뀐다. 정점u를 추가할 때 이미 그래프에 추가된 정점들에 대해서만 .. 2020. 2. 7.
BOJ 5719 - 거의 최단 경로 (다익스트라) https://suuntree.tistory.com/120?category=797985참고 https://www.acmicpc.net/problem/5719 참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다. 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라 1) 다익스트라https://suuntree.tistory.com/120?category=797985참고 https://www.acmicpc.net/problem/5719 참고 링크에서 설명한 아이디어를 그대로 갖다 사용하면 된다. 출발점 s에서 도착점 e로 갈때, 최단경로에 포함된 간선을 제외한 그래프에서 최단거리를 구해라 1) 다익스트라를 적용해서 dist배열을 초기화 한다. 2) 도착점 부터 역방향 인접배열를 사용해서 모든 .. 2020. 1. 27.
BOJ 10473 - 인간대포 (다익스트라) https://www.acmicpc.net/problem/10473 시작점, 끝점, 대포(최대 100개)의 좌표가 주어진다. 대포를 이용해서 시작점에서 끝점까지 가장 빠르게 이동하는 경우 그 시간을 구해라. 정점의 수가 극히 작으므로, 완전그래프라고 생각하고 풀어보자 정점 u는 좌표 (xu,yu) 정보를 가지고 있다. u->v일 때 가중치는 대포를 타지 않거나 대포를 타는 경우중 짧은 시간. 즉, min(distance(u,v)/5, 2+(distance(u,v)-50)/5) 이다. 단 시작점을 0번, 도착점을 n+1번이라고 할 때, 시작점에선 대포를 탈 수 없음에 유의해야 한다. typedef pair P; //정점의 정의 typedef pair PQ; //for pq const int MAX = 1e.. 2020. 1. 27.
BOJ 1162 - 도로포장 (다익스트라) https://www.acmicpc.net/problem/1162 정점의 상태를 잘 정의하고 정의된 정점 간의 간선이 어떻게 이어져있는지를 잘 파악하면 된다. 양방향 가중치 그래프가 주어진다. 연결된 간선에 대해서 최대 k번 가중치를 0으로 만들 수 있을 때, 정점 1에서 정점n으로 가는 최단길이는? u번 정점 전까지 도로포장을 t번했다면 정점을 (u,t)로 정의한다 (정점의 상태가 최대 20개라서 가능) u->v에 대해 (u,t) -> (v,t), (v,t+1) .. t+1 다익스트라로 풀 수 있다. typedef pair P; typedef pair T; const int MAX = 1e4 + 2; const ll INF = 1e18; vector adj[MAX]; ll dist[MAX][21]; i.. 2020. 1. 25.

티스토리툴바