최대 유량4 [자바] 백준 11378 - 열혈강호 4 (java - 풀이4개) 목차 문제 : boj11378 필요 알고리즘 개념 네트워크 플로우(최대 유량) 애드몬드 카프 등의 네트워크 플로우(최대 유량) 알고리즘을 알고 있어야 한다. 단, 자바의 경우 빠른 입출력까지 사용해야 애드몬드 카프 알고리즘으로 시간 초과 없이 통과 가능하다. 이분매칭 네트워크 플로우에서 이분 그래프로 구성이 가능할 시 사용 가능한 이분매칭 알고리즘을 사용하면 네트워크 플로우보다 더 빠른 시간내에 통과 가능하다. 이 경우엔 자바라도 빠른 입출력 없이도 여유롭게 통과 가능하다. 풀이 1과 풀이 2에서 최대 유량을 이용한 풀이를 한다. 풀이 3과 4에서는 이분매칭을 통해 풀어본다. 각 풀이는 네트워크 플로우 또는 이분매칭 알고리즘의 기본적인 구현 방식을 알고있다는 전제하에, k개의 추가된 일을 어떻게 처리하는.. 2022. 12. 18. [자바] 백준 6086 - 최대 유량 (java) 문제 : boj6086 필요 알고리즘 개념 네트워크 플로우 (최대 유량) 최대 유량 기본 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 에드몬드-카프 알고리즘을 사용해 최대 유량을 구했다. 에드몬드-카프 알고리즘을 적용할 수 있는 기본 문제로, 별도로 구현에 대해서는 풀이하지 않는다. 주의점은 입력으로 들어온 간선의 용량(capacity)이 양방향이라는 점이다. 즉, 'A B 3'과 함께 'B A 3'도.. 2022. 9. 25. [자바] 백준 17412 - 도시 왕복하기 1 (java) 문제 : boj17412 필요 알고리즘 개념 네트워크 플로우 (최대 유량) 최대 유량 기본 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 에드몬드-카프 알고리즘을 사용해 최대 유량을 구했다. 완전 기본 형태의 문제로, 간선이 존재하는 방향으로 용량(capacity)을 1로 잡고 알고리즘을 구현해주면 된다. 코드 : github import java.io.BufferedReader; import java... 2022. 9. 21. [자바] 백준 1671 - 상어의 저녁식사 (boj java) 문제 : boj1671 문제에서 제시된 상황이 그래프로 표현 가능한 경우 그래프로 바꿔서 생각해보는 것이 이득인 경우가 많다. 이 문제의 경우에도 주어진건 상어의 크기, 속도, 지능으로 3개나 되지만, 사실 그래프의 간선으로 생각해본다면 값이야 어떻든 조건을 만족한 경우 그냥 방향이 있는 간선 하나가 추가될 뿐이다. 예시 입력 1을 그려보면 다음과 같다. 간선은 [먹는쪽 -> 먹히는쪽]으로 연결할 것이다. 5 4 5 5 10 10 8 5 7 10 8 7 7 8 10 3 그럼 동일 정점을 좌우로 둬서 다음과 같이도 그려볼 수 있다. 결국 최대한 많이 잡아먹으면 남아 있는 수가 최소가 되므로, 최대유량 문제인데 이분그래프 이므로 이분매칭을 사용해서 좌측의 상어가 우측의 상어를 먹는다고 생각해보자. 그리고 좌.. 2022. 5. 26. 이전 1 다음
