이분매칭8 [자바] 백준 11377 - 열혈강호 3 (java) 문제 : boj11377 필요 알고리즘 개념 이분매칭 네트워크 플로우에서 이분 그래프일 시 사용 가능한 이분매칭 알고리즘을 통해 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N명의 직원이 M개의 일을 선택하는 것만 생각하자. 그럼 기본적인 형태의 이분매칭 알고리즘을 적용해서 풀 수 있다. 여기서 문제가 되는건 N명 중 K명은 일을 최대 2개할 수 있다는 점인데, 사실 약간의 아이디어만 추가하면 똑같다. .. 2022. 9. 17. 백준 2191 자바 - 들쥐의 탈출 (BOJ 2191 JAVA) 문제 : boj2191 이 문제에서 뭐' 속도가 빠른 쥐가 더 멀리 가야만한다'와 같은 가중치적인 부분은 들어있지 않다. N개의 정점을 M개의 정점에 최대한 많이 매칭 시키기만 하면 되는 문제이다. 1. 그래프 형태로 전처리 문제에서 제시된 값들만 가지고는 뭔가 풀어보기가 힘들다. 따라서 우선 그래프 형태로 변경해보자. 각 쥐의 현재 x, y 좌표와 각 땅굴의 x, y 좌표를 알고 있다. a번째 쥐의 좌표를 Xa, Ya라 하고, b번째 땅굴의 좌표를 Xb, Yb라 하겠다. 그럼 쥐가 땅굴로 달리기 전 a번째 쥐와 b번째 땅굴의 거리는 다음과 같다. 그리고 쥐는 초당 V만큼 움직이고, S초까지 들어가야 하므로 다음 식이 만족된다면 a번째 쥐에서 b번째 땅굴로 안전하게 들어갈 수 있다. ('단, 들쥐가 도착.. 2022. 3. 20. 백준 1298 자바 - 노트북의 주인을 찾아서 (BOJ 1298 JAVA) 문제 : boj1298 기본 형태의 이분매칭 문제이다. 그러니 푸는법을 모르겠다면 이분매칭에 대해 구글링해보면 풀 수 있다. 얼핏 이분 그래프가 아닌 것 같아 이분매칭을 적용하지 못한다고 생각할 수 있으나, 제시된 N이 결국 N명의 사람과 N개의 노트북 두개 모두를 뜻하므로 N개의 사람 정점과 N개의 노트북 정점이 이분 그래프를 이루게 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { StringTokenizer st; B.. 2022. 1. 6. 백준 2188 자바 - 축사 배정 (BOJ 2188 JAVA) 문제 : boj2188 완전 기본형태의 이분 매칭 문제이다. 이분 그래프임이 직관적으로 드러나므로 이분매칭 개념을 알고있다면 기본형 문제로 풀어볼만 하다. '예제 입력 1'을 그려보면 다음과 같다. 이분 매칭된 결과 중 최대로 매칭 시킬 수 있는 경우의 예시는 다음과 같다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { ArrayList[] edges; private int[] matched; private boolean[] .. 2022. 1. 5. 백준 1017 자바 - 소수 쌍 (BOJ 1017 JAVA) 문제 : boj1017 애초에 해결을 위한 키 아이디어도 일반적으로 찾기 쉽지 않을듯하고, 거기에 네트워크 플로우에서 이분 그래프의 최대 유량을 구하는 이분매칭 알고리즘에다가 소수 판정(에라토스테네스의 체)에다가 값 압축(이건 필수는 아님)까지 들어간 플래3에 손색이 없는 문제였다. 구현이 다소 복잡했어서 틀리면 예외찾을 엄두가 안났었는데 다행히 운좋게 한방에 통과했다. 오랜만에 한방에 통과한게 찐텐으로 기뻤다ㅋㅋ 1. 일단 브루트포스로 모든 경우를 살펴본다면 50C2번에 걸쳐 더해서 소수쌍이 되는걸 구하고, 모든 소수가 되는 쌍에 대해 모든 N개가 서로 겹치지 않고 선택되는 경우를 살펴야 한다. 대강 모든 쌍의 합이 소수가 된다면 O((50C2)!) 정도가 될 것이므로 통과할 수 없다. 서로 최대한 쌍.. 2022. 1. 4. 백준 11376 자바 - 열혈강호 2 (BOJ 11376 JAVA) 문제 : https://www.acmicpc.net/problem/11376 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11300/BOJ_11376.java 기본적인 형태의 이분 매칭 문제이다. 다만 한 사람당 2개의 일을 할 수 있으므로, n을 2배로 늘렸다. 이 때 간선 정보는 n개만 유지할 수 있도록 하는것이 좋다. 내 경우엔 그래서 간선정보를 n개 받아두고, e[n/2] (12line) 형태로 받아온다. 사실 이분 매칭에서 매칭시킬 때, 기본형태에서 그 안에 들어있는 n의 번호 자체는 중요한게 아니므로(같던 다르던 상관 없음) 코드의 45line처럼 for문 돌릴 필요 없이, 그냥 그 내에서 다시한번 2번을 돌리도록 해도.. 2021. 10. 17. 백준 11375 자바 - 열혈강호 (BOJ 11375 JAVA) 문제 : https://www.acmicpc.net/problem/11375 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11300/BOJ_11375.java 이분매칭에 응용같은걸 끼얹지 않은 기본형 문제이다. 따라서 단순히 '이분 매칭'을 공부해서 풀어도 바로 풀 수 있으며, 아이디어에 대한 힌트만 보려면 이 글(https://nahwasa.com/36)의 하위호환이므로, 이 글의 그림 있는 부분부터 보면 이 문제의 풀이 방식과 동일하다. 빨리 각 알고리즘이나 자료구조들에 대한 글을 써서 그런걸로 링크를 달면 깔끔할텐데.. 그런거 쓰려면 한편한편이 너무 오래걸린다 ㅠ 열심히 해야지.. 2021. 10. 16. 백준 18138 자바 - 리유나는 세일러복을 좋아해 (BOJ 18138 JAVA) 문제 : https://www.acmicpc.net/problem/18138 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/18100/BOJ_18138.java 일단하나씩 매칭시키는 문제이니 이분 매칭 문제인건 알겠는데, 그래프에 간선이 없다. 그러니 로직은 간단히, 1. 입력을 받는다 (init()) 2. 간선을 만든다 (makeEdge()) -> 이 때, w가 동일한게 안들어온다는 보장이 없으므로 w 대신 인덱스 번호로 새로 매칭시킨다. n개와 m개에 대해 0~n과 0~m을 노드로 하는 그래프로 바꾸면 된다. 간선을 만든 이후 w값은 필요없어진다. (62line) 3. 이분 매칭 돌린다 (matching()) 이분 매칭의 경우,.. 2021. 10. 16. 이전 1 다음
