본문 바로가기

이분 그래프

 (4)
[Python] 11668번 파이프 청소 https://www.acmicpc.net/problem/11668 24/05/12  기하학 + 그래프 이론 관련 문제이다. 좋은 문제인 것 같아서 풀이를 남겨보려고 한다. 문제 접근 방식:  문제에서 요구하고 있는 바를 정리해보자. 1. 파이프는 수원지와 도시를 잇는다.2. 두 파이프는 서로 교차할 수 있으며, 한 교차점에는 세 파이프가 동시에 교차하지 않는다.3. 교차점에는 이물질이 끼는데, 한 파이프에 로봇을 넣으면 그 파이프의 교차점을 모두 청소해 줌.4. 로봇이 충돌하는 일을 방지하기 위해 교차점에는 오직 하나의 파이프에만 로봇이 있어야 함.5. 어떤 파이프의 부분 집합을 잡아서 동시에 로봇을 투입했을 때, 두 로봇이 충돌하는 일이 없으면서 모든 교차점을 청소할 수 있는지를 판단해야 함.6. 두..
[Python] 19240번 장난감 동맹군 https://www.acmicpc.net/problem/19240 19240번: 장난감 동맹군 당신은 N개의 동물 장난감을 이용하여 모의 전쟁 놀이를 하려고 한다. 장난감은 편의상 1부터 N까지 번호가 붙어있고, 당신은 이를 두 개의 동맹군으로 나누고 싶다. 다만 특정 장난감끼리 사 www.acmicpc.net 24/03/16 이분 그래프임을 알아낸다면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 장난감을 그래프의 노드, 동맹이 될 수 없는 장난감의 쌍을 두 노드를 이은 간선이라고 간주한다면, 동맹이 될 수 없는 장난감 쌍 끼리는 서로 다른 동맹군이어야 한다는 조건은 이분 그래프의 조건을 만족한다. 따라서 주어진 그래프가 이분 그래프의 조건을 만족함을 알아내기만 하면 충분하다. 이는 DFS로 구현..
[Python] 25512번 트리를 간단하게 색칠하는 최소 비용 https://www.acmicpc.net/problem/25512 25512번: 트리를 간단하게 색칠하는 최소 비용 0번 정점을 black, 1번 정점을 white, 2번 정점을 white, 3번 정점을 black, 4번 정점을 black, 5번 정점을 black, 6번 정점을 black, 7번 정점을 white로 색칠하는 비용 310이 정답이다. www.acmicpc.net 24/02/08 간단한 그래프 탐색 문제로, 트리의 성질을 이용한 교육적인 좋은 문제다. 문제 접근 방식: 트리를 색칠할 수 있는 최소 비용을 문제에서는 요구하고 있고, 인접한 노드마다 항상 다른 색깔로 칠해야 한다는 제약 조건이 걸려있다. 요지는, 트리는 이분 그래프라는 점이다. 트리는 이분 그래프이기 때문에, 루트를 중심으로 ..
[Python] 1707번 이분 그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 22/11/14 전형적인 BFS, DFS응용 문제로, 이분 그래프에 대한 정의를 잘 알고 있기만 한다면 쉽게 풀 수 있는 문제이다. 이 문제에서는 BFS로 접근했으며, DFS로는 조금 귀찮을 것 같아 DFS로는 접근하지 않았다. 의외로 조금씩 틀렸었던 문제로, 문제를 잘 읽는 습관을 기르도록 하자. 문제 접근 방식: 처음에는 이분 그래프의 정의를 헷갈려서 틀렸습니다를 받았다. 어떤 식으로 이해했었..

티스토리툴바