BFS2 BOJ 15587 - Cow at Large (multisource bfs, dfs) https://www.acmicpc.net/problem/15587 트리가 주어진다. bessie의 위치 k가 주어진다. bessie를 쫓는 farmer들은 리프노드에서 출발한다. 모두 한번에 한칸씩 움직일 수 있을 때, bessie가 리프노드에 도달하지 못하도록 하려면 최소 몇명의 farmer가 필요한가? 모든리프노드 에서부터 멀티소스 플러드필을 해서 dist를 갱신해준다. dist[u] : u정점까지 어떤 farmer가 도착하기 까지의 시간. bessie의 초기 위치 k부터 dfs를 하며 현재 위치가 u 이동거리 d일 때, dist[u] n >> k; for (int i = 0, u, v; i > u >> v; adj[u].push_back(v); adj[v].p.. 2020. 2. 19. BOJ 15475 - A pie for a pie (이분그래프, 이분탐색) https://www.acmicpc.net/problem/15457 유사코 골드. bessie와 elsie가 서로 선물을 교환한다. 같은 선물에 대해 각자 생각하는 가치가 다를 수 있다. 최대 1e5개의 선물을 둘이 같은 개수만큼 가지고 있다. 서로 선물을 교환하려 한다. 예를들어, bessie가 볼때 3의 가치를 지닌 선물을 bessie가 받은 경우 3이상 3+d이하(bessie기준)선물을 elsie에게 보답으로 준다. elsie도 마찬가지다. 이런 방법으로 계속 선물을 교환할 때, 본인이 생각했을 때 가치가 0인 선물을 받으면 성공적으로 선물 교환이 이뤄진 것으로 본다. bessie부터 선물을 주기로 한다. bessie의 i번째 선물을 처음으로 elsie에게 줬을 때 가장 적은 횟수로 성공적인 선물교.. 2020. 2. 18. 이전 1 다음