네트워크 플로우 포드풀커슨 \(min(O(Ef),O(VE^2))\)네트워크 플로우 디닉 \(O(V^2E)\) 1. 잔여용량이 존재하는 간선을 따라 BFS하면서 정점들의 level을 매겨준다. s가 level 0- t의 level이 정해지지 않는다면 더 이상 증가경로는 없음. (현재 유량이 최대 유량) 2. s부터 DFS하면서 t에 도달할 때 까지 항상 level[u]+1==level[v] 를 만족하는 edge만 따라서 이동한다.- DFS 종료 하면서 유량 갱신해주고 더 이상 증가경로가 없을 때 까지 반복한다.- DFS 시 추가적으로 현재 몇 번 간선까지 사용하였는지 저장하는 배열을 이용해서 불필요한 탐색을 줄인다. 3. 더 이상 증가 경로가 없다면 1.로 돌아간다.
A. Bear and Big Brother 문제 Limak 와 Bob의 몸무게가 주어진다. Limak는 매년 3배씩 커지고 Bob은 2배씩 커진다. Limak가 Bob보다 커지기 위해서는 최소 몇 년이 지나야 하는지 구하는 문제이다. 문제 풀이 단순하게 1년 씩 늘리면서 2와 3을 각각 곱하고, Limak가 커질 때 출력하면 된다. 소스 코드 B. Bear and Friendship Condition 문제 친구 관계가 그래프로 주어진다. 한 컴포넌트내의 모든 정점이 서로 연결되어 있는지(완전 그래프)인지 판별하는 문제이다. 문제 풀이 각 정점마다 연결된 간선이 해당 정점이 포함된 컴포넌트 크기 - 1 인지 확인한다. 소스 코드 C. Bear and Different Names 문제 N명의 군인이 있고, ..
째로탈출 2 문제 N*M 보드에 파란 구슬 빨간 구슬 구멍이 한 개씩 있고, 상하좌우 4방향으로 기울일 수 있을 때, 최소 몇 번 만에 빨간 구슬이 구멍에 나올 수 있는지 출력하는 문제이다. 단, 파란 구슬이 구멍으로 같이 나오면 실패이다. 문제 풀이 최대 10번 까지 보드를 조작할 수 있으므로, BFS 탐색을 이용하면 각 상태 공간에서 상하좌우 4방향으로 전이 가능 하고, 한 상태 공간에서 해당 방향으로 최대 \(max(N,M)\) 만큼 이동할 수 있으므로 \(O(4^{10} max(N,M))\) 임을 알 수 있다. 따라서 각 상태 공간 내에서 한 방향으로 이동 할 때1. 빨간 구슬과 파란 구슬이 일직선 상에 없음1.1) 빨간 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 성공1.2) 파란 구슬이 가..