🔑 오늘의 학습 키워드 : 이분그래프
🔗 문제링크 https://www.acmicpc.net/problem/17834
import sys
from collections import deque
input = sys.stdin.readline
# 이분 그래프인지 아닌지 판별하는 함수
# 각각의 그룹도 같이 return
def is_bipartite(n,graph):
color = [None] * (n+1)
def bfs(start):
queue = deque([start])
color[start] = True
while queue:
node = queue.popleft()
for near in graph[node]:
if color[near] == None:
color[near] = not color[node]
queue.append(near)
# 갱신된 값이 이전 값이랑 같으면 이분 그래프가 아님
elif color[near] == color[node]:
return False
return True
for i in range (1,n+1):
if color[i] == None:
if not bfs(i):
return False, [] ,[]
true_group,false_group = [],[]
for i in range (n):
if color[i]:true_group.append(i)
else : false_group.append(i)
return True, true_group,false_group
def count_unending_positions(n, graph):
bipartite, true_group, false_group = is_bipartite(n,graph)
if not bipartite :
return 0
return len(true_group) * len(false_group) * 2
n, m = map(int, input().split())
bushes = [tuple(map(int, input().split())) for _ in range(m)]
graph = {i: [] for i in range(1, n + 1)}
for u, v in bushes:
graph[u].append(v)
graph[v].append(u)
print(count_unending_positions(n, graph))
🗒️ 공부한 내용 본인의 언어로 정리하기
🤔 문제를 보고 든 생각
이분 그래프라는 개념을 몰랐기 때문에 그냥 수학적으로 접근했었다.
당장 옆에 있으면 만나지 않는 경우가 되고, 2의 배수만큼 떨어질 때도 만나지 않는 경우가 된다고 생각했다.
노드의 개수가 홀수면 만날 수 있기 때문에 0을 return하고
노드의 개수가 짝수면 N ^ 2 // 2 를 하면 될 줄 알았다. 하지만 역시나 골드 1을 달랐다..
문제 알고리즘 유형을 보고 이분 그래프 알고리즘을 알게 되었고 이를 활용해서 풀어야겠다고 생각했다.
⏰ 예상 시간 복잡도 O(N * M )
제한 사항
첫 번째 줄에 수풀의 수 N(2 ≤ N ≤ 50,000)과 오솔길의 수 M(1 ≤ M ≤ 500,000)이 공백으로 구분되어 주어진다.
😎 알고리즘 개요
코드를 작성하기 전에 3가지로 나눴다.
1. 입력 부분
n, m = map(int, input().split())
bushes = [tuple(map(int, input().split())) for _ in range(m)]
graph = {i: [] for i in range(1, n + 1)}
for u, v in bushes:
graph[u].append(v)
graph[v].append(u)
양방향 그래프 형태로 바꿔 주었다.
2. 이분 그래프인지 판별하는 로직 부분
# 이분 그래프인지 아닌지 판별하는 함수
# 각각의 그룹도 같이 return
def is_bipartite(n,graph):
color = [None] * (n+1)
def bfs(start):
queue = deque([start])
color[start] = True
while queue:
node = queue.popleft()
for near in graph[node]:
if color[near] == None:
color[near] = not color[node]
queue.append(near)
# 갱신된 값이 이전 값이랑 같으면 이분 그래프가 아님
elif color[near] == color[node]:
return False
return True
for i in range (1,n+1):
if color[i] == None:
if not bfs(i):
return False, [] ,[]
true_group,false_group = [],[]
for i in range (n):
if color[i]:true_group.append(i)
else : false_group.append(i)
return True, true_group,false_group
bfs를 돌면서 현재 노드와 그 근처 노드의 부호를 다르게 바꿔가며 갱신해나갔다
1 - 2 - 3 이렇게 되었으면 True - False - True 이런식으로 갱신을 해나가는데
이때 이전에 갱신이 된 경우에 다시 밟을 때 전과 같으면 이분 그래프가 아니므로 False를 return한다.
그렇게 싸이클이 여러개가 있을 수 있기 때문에 모든 노드들에 대해 bfs를 적용해준다.
그 후 정답을 위해서 이 그래프가 이분 그래프를 만족하는지 여부와, true인 그룹과 false인 그룹을 나누어서 return해준다
3. 출력 부분
def count_unending_positions(n, graph):
bipartite, true_group, false_group = is_bipartite(n,graph)
if not bipartite :
return 0
return len(true_group) * len(false_group) * 2
2번에서 나온 결과를 가지고 출력을 해준다.
이때 토끼가 가능한 부분을 true_group, 사자가 가능한 부분을 false_group이라고 하면
각각 그룹에서 선택되는 경우 nC1 * nC1와 토끼가 false, 사자가 true인 경우 2가지를 해서 return을 해준다.
✅ 오늘의 회고
- 이분 그래프에 대해 알 수 있었다.
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
'Coding test' 카테고리의 다른 글
99클럽 코테 스터디 19일차 TIL, 프로그래머스 / 조이스틱 (0) | 2024.08.09 |
---|---|
99클럽 코테 스터디 18일차 TIL, 백준 / 일루미네이션 / 5547 (0) | 2024.08.08 |
99클럽 코테 스터디 16일차 TIL, 프로그래머스 / N-Queen (0) | 2024.08.06 |
99클럽 코테 스터디 15일차 TIL, 프로그래머스 / 소수 찾기 (0) | 2024.08.05 |
99클럽 코테 스터디 14일차 TIL, 프로그래머스 / 징검다리 (0) | 2024.08.04 |