[백준] 17471 게리맨더링 - 골드 3
[오늘의 문제]
https://www.acmicpc.net/problem/17471
[오늘의 학습 키워드]
- 백트래킹, BFS, 조합
1. 문제 설명
백준시는 N개의 구역으로 나뉘어져 있고, 구역은 1번부터 N번이 존재합니다.
구역을 두개의 선거구로 나뉘어 투표를 진행하려고 하는데 지역에 존재하는 사람수가 최대한 적게 차이가 나게 만드려고 합니다.
선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구로 포함된 지역은 모두 연결되어 있어야 합니다.
위 그림을 볼때 3번 그림이 불가능한 이유는 1, 2, 3, 4 지역은 연결되어 있어서 하나의 선거구로 볼 수 있는데 5, 6은 서로 떨어져 하나의 선거구로 볼 수 없기 때문입니다.
공평하게 선거구를 나누는 방법을 구하는 문제입니다.
[제한사항]
- 시간 제한 0.5초
- 메모리 제한 512MB
- 2 ≤ N ≤ 10
- 1 ≤ 구역의 인구 수 ≤ 100
2. 접근 방식
하나의 선거구는 모두 연결되어 있어야 하니 우선 BFS 탐색을 실시해 연결 여부를 확인하고 해당 지역의 주민수를 세어주면 될 것 같습니다.
문제는 선거구를 나누어야 하는데 나누는 방법이 문제입니다.
모든 선거구가 나뉘는 방법이 존재하므로
앞선 예시처럼 6개의 선거구가 존재한다고 하면 전체 탐색을 실시해 1번 대 나머지, 2번 대 나머지 이런식으로 모든 경우를 구해주어야 합니다.
또한 1번 대 나머지와 1번과 연결된 지역을 추가한 경우 등을 고려하여 코드를 작성해야 하니
백트래킹을 실시하고 백트래킹의 종료 조건에 BFS 탐색을 실시하여 결과를 가져오면 될 것 같습니다.
3. 코드
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
people = [0] + list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
# 입력받기
for i in range(1, N + 1):
node = deque(map(int, input().split()))
node.popleft()
graph[i] = list(node)
# ward 에는 연결된 지역번호가 담겨서 온다.
def BFS(ward):
queue = deque([ward[0]])
visited = [False] * (N + 1)
visited[ward[0]] = True
count_people = 0
range_ward = 1
while queue:
node = queue.popleft()
count_people += people[node]
for next_node in graph[node]:
if next_node in ward and not visited[next_node]:
visited[next_node] = True
range_ward += 1
queue.append(next_node)
if range_ward == len(ward):
return count_people
def DFS(n, count):
global answer
# 백트래킹 종료조건
if n == count:
A_ward, B_ward = [], []
for i in range(1, N + 1):
# 선거구를 구분할 건데 이미 방문한 곳은 A 아직 방문 안한곳은 B로 나누기
if visited[i] == True:
A_ward.append(i)
else:
B_ward.append(i)
# 나뉜 선거구를 기준으로 BFS 탐색
A_people, B_people = BFS(A_ward), BFS(B_ward)
# BFS 탐색해서 값이 있는 경우 해당 값의 차이로 answer 변경
if A_people and B_people:
answer = min(answer, abs(A_people - B_people))
# 종료
return
# 백트래킹 탐색 실시
else:
for i in range(1, N + 1):
if visited[i] == False:
visited[i] = True
DFS(n, count + 1)
visited[i] = False
answer = float('inf')
for i in range(1, N//2 + 1):
visited = [False] * (N + 1)
DFS(i, 0)
if answer == float('inf'):
print(-1)
else:
print(answer)[코드 설명]
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
people = [0] + list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
# 입력받기
for i in range(1, N + 1):
node = deque(map(int, input().split()))
node.popleft()
graph[i] = list(node)입력을 받아줍니다.
입력의 순서는 N개의 노드 수
노드별 사람의 수
N 지역과 연결된 노드의 갯수, 지역번호 가 입력됩니다.
입력 받을 때 노드와 연결된 지역의 갯수는 필요 없으니 deque를 이용해 popleft로 날려주고 나머지만 리스트로 형변환 하여 graph에 업데이트 해주었습니다.
answer = float('inf')
for i in range(1, N//2 + 1):
visited = [False] * (N + 1)
DFS(i, 0)앞서 1번 대 나머지, 2번 대 나머지 가 가능하였으니 모든 탐색 범위를 설정해 주어야 합니다.
근데 탐색을 실시하다 보면 결국 1번 노드를 기준으로 나머지 노드를 탐색하는데 해당 노드에 지역을 추가하는 방식으로 차이를 좁혀 나갑니다.
그럼 중복된 탐색이 존재하니 절반 정도만 탐색을 실시해 주었습니다.
또한 탐색마다 visited 배열을 새로 생성하여 모든 조건을 탐색 가능하도록 하였습니다.
def DFS(n, count):
global answer
# 백트래킹 종료조건
if n == count:
A_ward, B_ward = [], []
for i in range(1, N + 1):
# 선거구를 구분할 건데 이미 방문한 곳은 A 아직 방문 안한곳은 B로 나누기
if visited[i] == True:
A_ward.append(i)
else:
B_ward.append(i)
# 나뉜 선거구를 기준으로 BFS 탐색
A_people, B_people = BFS(A_ward), BFS(B_ward)
# BFS 탐색해서 값이 있는 경우 해당 값의 차이로 answer 변경
if A_people and B_people:
answer = min(answer, abs(A_people - B_people))
# 종료
return
# 백트래킹 탐색 실시
else:
for i in range(1, N + 1):
if visited[i] == False:
visited[i] = True
DFS(n, count + 1)
visited[i] = FalseDFS로 작성한 백트래킹 코드입니다.
가장 먼저 백트래킹의 종료 조건을 작성해 주었습니다.
탐색을 시작할 노드와 탐색 횟수가 동일해지면 종료하도록 하였습니다.
만약 종료 조건을 만족하지 못하는 경우 백트래킹 탐색을 실시하는데 모든 조건을 탐색하며 백트래킹으로 돌아야 하니 DFS 실시 후 visited를 다시 초기화 하여 조건을 맞춰 주었습니다.
종료 조건에 만족하는 경우 이제 선거구를 나누어 주어야 합니다.
현재까지 백트래킹으로 탐색을 하면서 방문한 지역, 즉 서로 연결된 지역을 하나의 선거구로 몰아주어야 합니다.
그리고 나머지를 또 하나의 선거구로 몰아 주어 두개의 선거구를 생성해 줍니다.
해당 선거구를 기준으로 모두 연결되어 있는지를 파악하기 위해 BFS 탐색을 실시합니다.
BFS 탐색 결과로는 해당 선거구의 주민 수를 반환할 것이기에 BFS 탐색의 결과를 주민 수로 받아줍니다.
# ward 에는 연결된 지역번호가 담겨서 온다.
def BFS(ward):
queue = deque([ward[0]])
visited = [False] * (N + 1)
visited[ward[0]] = True
count_people = 0
range_ward = 1
while queue:
node = queue.popleft()
count_people += people[node]
for next_node in graph[node]:
if next_node in ward and not visited[next_node]:
visited[next_node] = True
range_ward += 1
queue.append(next_node)
if range_ward == len(ward):
return count_peopleBFS 탐색을 실시하는데 입력된 ward에는 선거구가 포함되어 있습니다.
즉 선거구의 모든 지역번호가 담겨 있는 것입니다.
BFS 탐색의 위치는 항상 가장 먼저오는 노드를 기준으로 고정하여 탐색을 실시하는데 여기서도 visited 배열을 생성하여 연결 여부를 파악하며 중복을 없애 줄 겁니다.
이때 count_people 과 range_wrad 를 생성해 주었는데 count_people 는 현재 선거구의 주민수를 모두 더해서 반환하기 위한 변수이고 range_wrad는 현재 선거구를 2개로 구분햇는데 입력받은 선거구의 길이에 맞게 탐색을 종료하기 위해서 생성해 주었습니다.
queue에 ward의 첫번째 값을 넣고 탐색을 실시하는데
이때 현재 node를 기준으로 주민 수를 세어 count_people에 더해줍니다.
또 graph에 모든 노드의 연결정보가 담겨 있으니 graph에 node번호를 가져와 연결 정보를 가져오고 그걸 next_node로 지정합니다.
여기서 다음 노드는 방문하지 않아야 하고 다음 노드는 내가 구분한 선거구에 포함된 지역이어야 합니다.
next_node에 방문하지 않은 경우 방문 처리를 하며 queue에 넣어줍니다.
그러고 탐색한 지역의 갯수를 세어줍니다.
탐색을 실시하다 탐색할 모든 지역을 탐색한 경우 종료하며 현재까지 세어준 주민수를 반환합니다.
그럼 그 결과가 A_people 과 B_people에 담기겠죠
만약 연결되지 않았다면 그대로 0을 반환 할 겁니다.
그래서 결과를 출력하는 코드를 다음과 같이 작성했습니다.
# BFS 탐색해서 값이 있는 경우 해당 값의 차이로 answer 변경
if A_people and B_people:
answer = min(answer, abs(A_people - B_people))
# 종료
return백트래킹은 값이 있든 없든 n이 count와 동일해지면 무조건 탐색을 종료하고 상위로 올라갈 겁니다.
그때 값이 people 값이 둘다 있는 경우 그 차이를 찾아서 최소값으로 바꿔주는 겁니다.
그 후 정답을 출력하는데 만약 값이 바꼇다면 그 차이를 출력하고 바뀌지 않은 경우는 선거구를 나눌 수 없는 경우이니 -1을 출력해 줍니다.
4. 결과
[회고]
사실 문제를 해결하기 위한 조건은 잘 세웠었는데 이걸 코드로 작성하기 위해서 고민을 많이 했습니다.
두 선거구로 나누고 BFS 탐색을 돌릴건데 선거구를 어떻게 나누지에서 막혔었는데
곰곰이 생각을 하니 우선 전체 지역을 기준으로 모든 지역대 나머지 지역이 나올 수 있으니 전체 탐색을 실시합니다.
그러다 해당 선거구를 방문처리하며 모든 경우의 수를 구해야 하니 백트래킹을 써야겠네 라는 결론이 나왔고
백트래킹의 기본 구조를 먼저 잡고 코드를 천천히 작성했습니다.
가장 먼저 종료조건을 설정하고 그게 아닌경우 재귀를 할 수 있도록 함수안에 함수를 작성했습니다.
거기에 종료조건에 맞출 수 있도록 조건을 설정하여 탐색을 하는데 모든 경우의 수를 구해야 하닌 방문 배열을 사용하기로 하고 탐색한 경우와 탐색하지 않은 경우 중복을 최소화 할 수 있었습니다.
그 다음은 백트래킹의 종료조건을 만족하는 경우 즉 두 선거구로 나누었단 경우이고
나눈 선거구를 기준으로 a b로 나눠 주어야 했습니다.
나누고 나서 BFS 탐색을 해서 연결여부를 확인하고 연결된 부분까지 탐색하여 사람수를 반환하면 되겟다 싶었습니다.
그러면서 중간에 탐색을 종료해야 하는 경우가 생겼습니다.
선거구를 기준으로 BFS는 연결된 모든 선거구를 탐색을 할 거니까 내가 구분한 만큼만 탐색을 해야 하는데
그럼 입력받은 선거구의 길이 까지만 탐색을 하되 들어온 노드번호가 있어야 겠다 싶어서 range_ward를 생성하였고 문제를 해결할 수 있었습니다.
하나하나 풀어나가다 보니 생각보다 재밌게 풀었고 이전에 알고리즘 풀었던 기억도 나면서 적당한 난이도 였다고 생각합니다.