1. 문제
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/
참고로 비트연산자로 부분집합 구했다는 말을 하니 하늘님이 다른 방법도 소개해줘따
그럼 이만 ~!
'Algorithm > Python' 카테고리의 다른 글
[알고리즘] 순열 (0) | 2021.02.07 |
---|---|
[백준 16236] 아기 상어 (2) | 2021.02.03 |
[백준 20055] 컨베이어 벨트 위의 로봇 (0) | 2021.02.02 |
[백준 17070] 파이프 옮기기 1 (0) | 2021.01.31 |
[백준 1929] 소수구하기 (1) | 2021.01.31 |