![]()
문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 조합론, 너비 우선 탐색, 깊이 우선 탐색, 브루트포스 알고리즘 주어진 선거구에서 임의로 몇 개를 선택하여 A구역으로 설정하고, 선택하지 않은 구역은 B구역으로 설정한다. N이 최대 10이므로 모든 경우의 수를 비교해도 시간 초과는 발생하지 않는다. 선거구를 선택할 때는 깊이 우선 탐색의 방식으로 1번 선거구를 선택하고 계산한 다음, 다시 해제하는 방식으로 진행한다. 선택한 선거구가 문제의 조건을 만족하는지 확인해야 한다. 구역은 2개로 나뉘어져야 하므로, 선택한 선거구가 ..
![]()
문제 풀이 DFS와 백트래킹을 사용한다. 지나온 알파벳을 확인할 vector를 생성하여 다음으로 지나갈 칸을 확인한다. 코드 #include #include #include using namespace std; int R, C; char board[21][21]; int move_x[4] = { 0, 0, 1, -1 }; int move_y[4] = { 1, -1, 0, 0 }; int answer = 0; void dfs(int x, int y, int dist, vector& alphabets) { answer = max(answer, dist); bool flag = false; for (int i = 0; i < 4; ++i) { int next_x = x + move_x[i]; int next_..
