본문 바로가기
728x90

백준플래/Graph13

백준 1348, 주차장 개요 문제 링크 플래 2, Graph, Bipartite matching, BFS 모든 C가 P로 이동하기 위한 최소 시간 구하기 접근 특이한 이분매칭 문제. 이분매칭을 모른다면 꼭 숙지한 다음 문제를 접근하길 바란다. 안그러면 시작을 할 수 없다. 태그에 이분탐색이 있는데 어떻게 쓰느냐 하면 시간에 대해 쓴다. 시간의 기준은 모든 차의 주차가 되느냐? 하는 것이다. 왜냐? 시간이 0일때를 생각하면 모든 차가 주차가 안된다. 시간이 한 100만쯤 되면 모든 차를 주차할 수 있다. 시간을 계속 늘려가면서 뇌뮬레이션을 돌려보자. 계속 주차가 안되다가 어느 시점부터는 계속 된다. 이 변화하는 지점을 찾아보자는 것이다. 시간을 함수의 입력으로 넣자니 너무 번거롭다. 복잡하게 하지 말고 전역변수로 때려버리자. 이.. 2023. 3. 15.
백준 14398, 피타고라스 수 개요 문제 링크 플래 3, Graph, Bipartite matching, 정수론 서로소인 두 수를 직각삼각형의 빗변이 아닌 두 변이 되도록 짝 지을 때, 가장 많은 짝의 수 구하기 접근 재미진 이분매칭 문제. 이런 새로운 알고리즘은 한 번 배우면 응용이 무궁무진해서 티어올리기 좋다 재미를 더해준다. 이분매칭을 모른다면 꼭 공부하자. 내용을 모르면 시작을 할 수가 없고 브루트포스를 돌려서 200!번의 연산을 하는 수밖에 없다. 소수 쌍 문제와 유사한데, 비슷하게 이분과 매칭에 대해 생각해보자. 이분을 어떻게 해줘야 할까? 이 문제는 엄청 특이하게 현재 집합을 두개로 쪼개지 않고, 복사해버리면 된다. 연결 조건은? 우선 서로소이고, 두 수의 제곱의 합이 어떤 자연수의 제곱이 되면 된다. 즉 sqrt(a×a.. 2023. 3. 15.
백준 1017, 소수 쌍 개요 문제 링크 플래 3, Graph, Bipartite matching, 정수론 모든 두 수를 짝지어 소수를 만들 때, 첫 수와 짝지어지는 수 출력하기 접근 유서깊은 이분매칭 문제. 대체 이게 어떻게 이분매칭일까 싶은데 하나하나 뜯어보면 소름돋는 이분매칭 문제이다. 이분매칭을 모른다면 꼭 무슨 내용인지를 알고 접근하는 것이 좋다. 아니면 시작을 할 수가 없다. 이분이 되는 이유는? 짝수와 홀수를 이분해주면 된다. 매칭이 되는 이유는? 둘을 매칭시켜야 하는데 만약 짝-짝, 홀-홀 매칭이면 그 합이 짝수이기 때문에 소수가 될 수 없다. 따라서 이분, 매칭에서 짝,홀로 이분하고 각각을 매칭해주는 것이 이 문제의 핵심이 된다. 그럼 우선 이분을 해주자. 개인적으로 이걸 구현하는게 제일 헷갈렸다. 처음 들어온 .. 2023. 3. 15.
백준 14433, 한조 대기 중 개요 문제 링크 플래 4, Graph, Bipartite matching 최대한 많은 사람이 트롤픽을 하도록 N명의 사람이 M개의 트롤픽을 할 때 두 팀의 트롤픽 비교하기 접근 이분매칭 을 사용하는 문제. 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. 문제 지문이 길고 복잡해서 이해가 살짝 어려울 수 있는데, 일단 두 팀은 최대로 많은 트롤픽이 나오도록 선택을 하므로 둘 다 최대 유량을 구하는 문제임은 맞다. 그럼 다음은 트롤픽 개수를 비교하는 것인데, 동점이면 안되니까 무조건 첫 팀의 트롤픽이 적어야 한다. N개의 사람 그룹과, M개의 트롤픽 그룹이 있고, 그래프의 모든 연결관계는 사람과 트롤픽을 연결하므로 이분 그래프의 .. 2023. 3. 15.
백준 2191, 들쥐의 탈출 개요 문제 링크 플래 4, Graph, Bipartite matching N마리의 쥐가 M개의 굴에 들어갈 때 시간 내에 들어갈 수 있는 최대 쥐 수 구하기 접근 이분매칭 을 사용하는 문제. 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. 이게 이분매칭인 걸 모르면 좀 많이 답답할만한 문제인데, 핵심은 모든 쥐마다 각자 들어갈 수 있는 구멍을 미리 구해놓는 것이다. 이러면 갑자기 이분매칭 문제로 변한다. 들어갈 수 있는 조건은? 거리가 S×V보다 작으면 된다. N개의 쥐 그룹과, M개의 구멍 그룹이 있고, 그래프의 모든 연결관계는 구멍과 쥐를 연결하므로 이분 그래프의 매칭 문제가 된다. 나머지는 이분매칭을 잘 이해하고 있다면 .. 2023. 3. 15.
백준 17481, 최애 정하기 개요 문제 링크 플래 4, Graph, Bipartite matching N명의 사람이 M명의 최애가 있을 때 최대한 많은 사람이 최애를 선택하게 만들기 접근 이분매칭 을 사용하는 살짝 씹덕틱한 문제. 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. N개의 사람 그룹과, M개의 최애 그룹이 있고, 그래프의 모든 연결관계는 최애와 사람을 연결하므로 이분 그래프의 매칭 문제가 된다. 엥 그런데 이분매칭은 정수로 하는거 아님? 이럴 때는 고민말고 C++의 미친장점, map을 쓰면 된다. map에는 각 이름의 맞는 index를 저장해둔다. 나머지는 이분매칭을 잘 이해하고 있다면 크게 어렵지 않다. 원하는 최애 중 아직 아무도 선택 안.. 2023. 3. 15.
백준 1298, 노트북의 주인을 찾아서 개요 문제 링크 플래 4, Graph, Bipartite matching N명의 사람이 M개의 노트북을 원할 때 최대한 많은 사람 만족시키기 접근 이분매칭의 대표적인 문제, 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. 11375와 마찬가지로 N개의 사람 그룹과, M개의 노트북 그룹이 있고, 그래프의 모든 연결관계는 노트북과 사람을 연결하므로 이분 그래프의 매칭 문제가 된다. 나머지는 이분매칭을 잘 이해하고 있다면 크게 어렵지 않다. 원하는 노트북 중 아직 아무도 선택 안했거나, 원래 주인을 내쫓을 수 있으면 자기가 선택하면 된다. Pseudo code can(a) { // 원하는 노트북 중 for (b:graph[a]) /.. 2023. 3. 15.
백준 11376, 열혈강호 2 개요 문제 링크 플래 4, Graph, Bipartite matching N명의 사람이 M개의 일을 최대 2번까지 할 때 최대 일의 수 접근 이분매칭의 대표적인 문제, 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. 11375와 마찬가지로 N개의 사람 그룹과, M개의 일 그룹이 있고, 그래프의 모든 연결관계는 일과 사람을 연결하므로 이분 그래프의 매칭 문제가 된다. 그런데 일을 두 개씩 하는 경우를 어떻게 따져줄까? 정해는 사람을 복제해서 두명으로 만들어주면 되는 것인데 이게 왜 되냐면, 어떤 사람과 그 복제본을 A,A'이라고 하면, A,A'은 연결관계가 같고, 서로 같은 일을 선택하지 않는다. 즉 한 명이 두 .. 2023. 3. 15.
백준 2188, 축사 배정 개요 문제 링크 플래 4, Graph, Bipartite matching N마리의 소를 M개의 축사에 한 마리씩 들여보내기 접근 이분매칭의 대표적인 문제, 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. N개의 소 그룹과, M개의 축사 그룹이 있고, 그래프의 모든 연결관계는 소와 축사를 연결하므로 이분 그래프의 매칭 문제가 된다. 나머지는 이분매칭을 잘 이해하고 있다면 크게 어렵지 않다. 코드는 11375와 N을 제외하고 완벽히 똑같다. Pseudo code can(a) { // 들어갈 수 있는 축사 중 for (b:graph[a]) // 비어있는 축사이거나 // 이미 있는 소를 내쫓을 수 있을 때 if (!B[b]||can(B[b])) { A[a]=b,B[.. 2023. 3. 15.
백준 11375, 열혈강호 개요 문제 링크 플래 4, Graph, Bipartite matching N명이 M개의 일을 하나씩만 할 때 최대로 할 수 있는 일의 개수 구하기 접근 이분매칭의 대표적인 문제, 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. N개의 사람 그룹과, M개의 일 그룹이 있고, 그래프의 모든 연결관계는 사람과 일을 연결하므로 이분 그래프의 매칭 문제가 된다. 나머지는 이분매칭을 잘 이해하고 있다면 크게 어렵지 않다. Pseudo code can(a) { // 연결되어있는 것 중 for (b:graph[a]) // 아직 연결안했거나 재연결이 될 때 if (!B[b]||can(B[b])) { A[a]=b,B[b]=a return 1 } return 0 } match(.. 2023. 3. 15.
728x90

티스토리툴바