백준 17471_게리맨더링(C++)
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net [문제 풀이] 브루트 포스(Brute force)를 이용하여 문제를 풀었습니다. 이 문제는 주어진 입력을 두 집합으로 나누었을 때 나누어진 집합이 그래프로 연결 되어 있는지를 찾는 문제였습니다. 예를 들어 두 집합 A ={ 1, 2, 3 }, B = { 4, 5, 6 }으로 나누었을 때 A의 노드들이 A의 노드를 통해서 모두 연결 되어 있어야 합니다. 반대로 B 또한 마찬가지입니다. 파란색 집합의 원소 5가 B의 노드를 통해 6으로..
백준 2468_안전 영역(C++)
www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net [문제 풀이] BFS를 이용하여 문제를 풀었습니다. 이 문제는 물이 0부터 무한대 높이의 비가 내렸을 때, 상, 하, 좌, 우로 서로 연결된 안전 영역의 최대 개수를 구하는 문제입니다. 안전 영역이란 문제 예제에서 높이가 4인 비가 내렸을 때 (0, 0), (0, 1)의 땅은 침수당하지 않습니다. 따라서, 강수량이 4인 경우 좌표 두 개를 묶어 {(0, 0,), (0, 1)} = 안전 영역 하나가 되는 것입니다. 문제..
