오딩이

문제 : https://www.acmicpc.net/problem/13265 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 🔍 Solve SWEA와 문제 유형이 비슷하게 제일 먼저 테스트 케이스의 개수가 주어집니다. 해당 입력을 테스트케이스별로 나누면 아래 그림과 같이 예제를 나눌 수 있습니다. 이 중 테스트케이스 1번을 그래프로 그려 두 가지 색으로 칠해보면 다음과 같이 불가한 경우를 찾을 수 있습니다. 따라서 문제를 해결하기위해 color 일차원 배열을 사용하였습니다. 두 가지 색의 예시를 빨간색과 파란색이라고 해봅시다. co..

출처 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 🔍 Solve 조합을 이용한 완전 탐색이며, dfs를 사용했습니다. 다음과 같은 순서로 구현했습니다. 1. 그래프(배열) 만들기 - 조합 2. 선거구 연결 - 그래프 탐색(dfs) 3. 인구수 파악 부분집합이 아닌 조합을 사용한 이유는, 배열 1이 뽑혔으면 배열 2는 배열 1의 여집합이기 때문에 부분 조합을 사용하면 중복되는 배열이 반환됩니다. 따라서 1부터 N/2까지의 개수를 뽑는 조합을 사용했습니다. 조합..