[백준 17471] 게리맨더링

1. 문제

 

www.acmicpc.net/problem/17471

17471번: 게리맨더링

2. 접근방법

 

처음에 문제 이해하는게 어려웠심다 

몇번을 읽었는지 .. ;ㅁ;

한국어가 부족한가봅니다요

근데 풀어서 지금 신나요 신나는 마음에 바로 포스팅하러 달려왔습니다

 

뭐여튼 무튼 글자 그대로 차근차근 따라가보면

엇 이거 어떻게 해야하지 싶은뎁쇼

 

1. 인접하다는 것을 어떻게 파악하지 => 인접리스트, 인접행렬

2. 2개로 어떻게 나누지 => 부분집합

 

으로 생각했습니당

 

주로 부분집합 문제 풀 때

귀찮아서 `import itertools`를 쓰는데용

 

SWEA는 그것을 허용하지 않는 다는 말에 다른 방법을 고안했습니다

 

그것은 바로바로바로바로바로바로바로 비트 연산자를 사용하는 것 !비트 연산자를 처음 접했을 때심교수님을 붙잡고 얼마나 질문을 했는지기억이 나는데

 

중요한건 비트 연산자가 기억이 안나는거쥬 ..

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

뭐 여튼 ..

 

오늘은 그래서 비트 연산자로 부분집합 생성하기를 잠시 다뤄보겠습니다

---

arr = [1, 2, 3]
n = len(arr)

for i in range(1<<n):
	for j in range(n):
    	if i & (1<<j):
        	print(arr[j], end=" ")
    print()
    
 # 1
 # 2
 # 1 2
 # 3
 # 1 3
 # 2 3
 # 1 2 3

요런 형태이구여 (코드 블록이 왜 자기 멋대로 들여쓰기를 하는지 ..🙄🤔 흠 ~! 아직은 티스토리가 어렵네용)

 

이거는 2진법을 이용해 부분집합을 알아내는 것입니다

 

1. 2진법을 사용하게 되면 !!

3 2 1이 각각 [0 0 0] 이렇게 자기 위치에 대립되어서

 

[0 0 1]인 경우 1[0 1 0]인 경우 2[1 0 0]인 경우 3[0 1 1]인 경우 1, 2[1 1 0]인 경우 2, 3[1 0 1]인 경우 1, 3[1 1 1]인 경우 1, 2, 3

 

을 나타내게 됩니다

 

2. << 비트 연산자

1 << n 이 의미하는 것은

왼쪽에 위치한 숫자 '1'을 2진수로 보고

n번 왼쪽으로 shift하라는 뜻입니다.

 

이렇게 된다면

2진수 <==> 10진수 로 표현하면

1 <==> 1

10 <==> 2

100 <==> 4

1000 <==> 8

...

이런 식으로 2진수 자릿 수가 하나씩 증가할 때마다 십진수 기준으로 2가 곱해지겠죠 ~!

 

그럼 결국 우리는

1<<n이 2^n과 같다.

라는 결론에 도달할 수 있습니다.

 

우리는 부분집합의 총 갯수가 2^n이라는 것을 알기에 ..

 

삼단논법에 의거하여 ^^

1<<n은 원소의 갯수가 n개인 부분집합의 총 갯수이다.

요런 결론이 나온거쥬

 

그럼 우리가 사용한 코드 중

for i in range(1<<n):

은 결국

for i in range(2**n)

과 같은 친구였습니다 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

3. & AND

&은 AND를 찾는 비트연산자입니다요찾는다는 표현이 맞나 ??? 음 ~!

 

일단 한 번 사용해보면서 &을 느껴보러 가시죵

 

A&B는 A와 B의 2진수 형태에서 공통된 값을 10진수로 변환해 리턴합니다.

 

ex) 입력 : print(5&4) ==> 출력 : 4

 

왜 5와 4의 공통된 값은 4일까요 ? ? ? ? ?  단순히 4가 더 작아서 포함된걸까요 ? ? ? ? ?(약간 킹리적 갓심 ..)

 

단호한 놉

5와 4를 2진수로 나타내면

5의 경우 101

4의 경우 100 입니다.

 

여기서 공통된 값이라함은 같은 숫자인데요 !!!!!

 

5와 4 모두 첫번째, 두번째 자릿 수가 10으로 시작합니다.

그리고 마지막인 세번째 자릿수가 각각 1과 0으로 다른데요 ???

 

이렇게 되면 공통된 값은 100이 되는 거쥬  !!!!!!!!!!!!!!!!!! 

 

그럼 2진수 100을 십진수로 변환하면 ? ??  ?? ? 

정답은 4입니다 !!!!!!!!!!!!!!!

 

이렇게 되어서 print(5&4)는 4가 되는 겁니다요

 

4. 총정리

자아아아아 그럼 이제 

arr = [1,2,3]
n = len(arr)

for i in range(1<<n):
    for j in range(n):
        if i & (1<<j):
            print(arr[j], end=' ')
    print()

이 친구를 다시 봐봅시다.

무슨 너낌인지 느껴보자구욧 !!

 

우리는 n에 arr리스트 원소 갯수를 담았습니다.

 

그리고 첫번째 for문에서 1<<n만큼 반복하자고 하는데요 ???

이것은 !!! 결국 !!! arr의 부분집합 갯수 만큼 반복하자는 거 !! 이제 보이시나욤

 

그리고 그 다음 for문은 arr의 원소 갯수 만큼 반복을 합니다

이 반복문을 쓰는 이유는 그 다음 if문을 사용하기 위해서인데요

 

if i & (1<<j)

-> 이 친구가 참 .. 그래요 ..

이거는 i와 1<<j를 2진수로 변환해서 동일한 값 부분을 리턴할 경우 라는 말이죠 ?

 

여기서 i는 부분집합을 뜻하는거라고 위에서 말했쥬 ??

-> 근데 우리는 총 부분집합 갯수 중에서 i번째인거니까 ! 얘는 부분집합의 idx입니다

그리고 j는 원소의 갯수 중 하나잖아염 ?

1<<j를 하게 되면

첫 번째 원소의 경우 (그러니까 맨 왼쪽 원소, idx가 0인 원소)

1<<0이기 때문에 1이구요

 

두 번째 원소의 경우

1<<1이기 때문에 10(2진수 표현)이구요

 

세 번째 원소의 경우

1<<2이기 때문에 100(2진수 표현)입니다.

 

그럼 이제 보이시나용

 

i번째 부분집합을 찾는 문장이었씁니다 !!!!!!!!!!!!!!!!

그럼 이제 끄읏 바이바이

---

다시 본론으로 돌아가서

 

위의 방식대로 부분집합을 구해서 두 구역으로 나눴습니다.

1. 부분집합 구하기

2. 공집합 제외하기

3. 부분집합의 여집합 구하기 (얘는 if문에서 else문도 만들어서 list에 append해주면 됩니다요)

 

그리고 나서 각 구역이 이어졌는지 확인했습니다.

 

확인은 당연 ~! 말해뭐해 ~! DFS/BFS 중 하나라고 생각했구욧

 

주로 인접한 거 찾을 때는 BFS를 사용하기 때문에 queue를 사용해야겠다는 생각을 했습니다

 

그래서 queue를 사용하기 위해 deque를 불러왔구요 (이건 또 가능임ㅋ_ㅋ)

 

참고로 최근에 deque의 위대함을 느낀 문제가 있었는데 언젠가 포스팅하겠죠 ? (www.acmicpc.net/problem/7562)

 

 

여튼 그래서 deque를 사용했구요순회하면서 같은 팀 친구가 있는지 확인 .. 있으면 그 친구 방문 체크 해주고 queue에 넣고 .. 뭐 요런식으로 했슴다.

 

참고로 넣을 때는 extend썼습니다append는 리스트 그대로 들어가지만extend는 리스트의 원소만 넣어주기 때문에 ..

 

제 코드 제 맘대로 짤래욧!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

여튼 그렇게 하고 .. 순회하고 ..언젠가 break를 해야하는데 언제하지 하다가 ..visit를 숫자 배열로 만들어서sum으로 체크할 수 있ㄱㅔ끔 만들었습니다.

 

이거는 코드를 보면 이해가 바로 될 것이라 믿으며 ..

 

일단 문제 풀 때 사용한 필기는 요고입니다요

 

3. 파이썬 코드

 

from collections import deque

def bfs(lst):
    if len(lst) == 1:
        return True
    global N
    visited = [0] * (N+1)
    visited[lst[0]+1] = 1
    q = deque(board[lst[0]+1])
    while q:
        if sum(visited) == len(lst):
            return True
        next_num = q.popleft()
        if visited[next_num] == 0 and next_num-1 in lst:
            visited[next_num] = 1
            q.extend(board[next_num])
    return False

N = int(input())
people = list(map(int, input().split()))
board = [[] for _ in range(N+1)]
ans = 1e9

for i in range(N):
    tmp = list(map(int, input().split()))
    board[i+1] = tmp[1:]

for i in range(1<<N):
    sum1, sum2 = 0, 0
    tmp1 = []
    tmp2 = []
    for j in range(len(people)):
        if i&(1<<j):
            tmp1.append(j)
            sum1 += people[j]
        else:
            tmp2.append(j)
            sum2 += people[j]

        if len(tmp1) == N or len(tmp2) == N or len(tmp1) + len(tmp2) != N:
            continue
        if abs(sum1 - sum2) < ans:
            if bfs(tmp1) == True and bfs(tmp2) == True:
                ans = abs(sum1 - sum2)

if ans == 1e9:
    print(-1)
else:
    print(ans)

 

4. 마치며

 

골드 공포증있는데 ..

 

자꾸 골드 올려주시는 모든 분들에게 감사 ..

압도적 감사 ..

 

이전사비 .. 화이륑 ..!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

소심한 .. 압도적 감사

 

부분집합 참고한 포스팅 : itzjamie96.github.io/2020/10/15/python-bitwise-powersets/

[Python] 비트연산자로 부분집합 구하기 - Code with Jamie

참고로 비트연산자로 부분집합 구했다는 말을 하니 하늘님이 다른 방법도 소개해줘따

 

맞습니다요

 

그럼 이만 ~!