[PS] BOJ 1953 / 팀배분
![[PS] BOJ 1953 / 팀배분](/content/images/size/w2000/2025/11/-------------2.png)
문제 링크: https://www.acmicpc.net/problem/1953
이분 그래프를 활용하는 문제입니다.
풀이
이분 그래프란?
서로 인접한 두 정점을 다른 색상으로 칠할 때, 전체 그래프의 모든 정점이 두 가지 색으로 표현되는 그래프를 말합니다. 그래프 탐색을 통해 그래프의 각 정점을 2가지 색상으로 칠해 주어진 그래프가 이분 그래프인지 아닌지를 알 수 있습니다.
자세한 설명은 이전 글을 참고해주세요 😀
풀이
문제에서 주어지는 그래프는 항상 이분그래프이며, 모든 사람이 싫어하는 사람이 단 한 명도 없는 경우는 없습니다. 항상 문제 조건에 맞는 데이터만 주어지기 때문에, 이분 그래프에서의 그래프 탐색으로 쉽게 풀 수 있습니다.
BFS를 통해 주어진 그래프의 각 정점에 1 또는 -1로 번호를 매긴 뒤, 매긴 번호를 기반으로 두 팀에 소속된 인원을 출력했습니다.
전체 코드
from collections import deque
input = open(0).readline
N = int(input())
graph = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
E, *verticies = map(int, input().rstrip().split())
for v in verticies:
graph[i].append(v)
graph[v].append(i)
# BFS로 이분 그래프 색칠하기
team_number = [0] * (N + 1)
queue = deque()
def bfs(src):
queue.clear()
queue.append(src)
team_number[src] = 1
is_bipartite = True
while is_bipartite and queue:
u = queue.popleft() # 정점의 깊이를 기준으로
for v in graph[u]:
if team_number[v] == 0: # 새로 방문하는 정점
team_number[v] = -team_number[u]
queue.append(v)
elif team_number[v] + team_number[u] != 0: # 이분 그래프가 아니게 되는 경우: 인접한 정점과 같은 색으로 칠해질 때
is_bipartite = False
break
return is_bipartite
for i in range(1, N + 1):
if team_number[i] == 0:
bfs(i)
team_members = ([], [])
for i in range(1, N + 1):
if team_number[i] == 1:
team_members[0].append(i)
else:
team_members[1].append(i)
print(f"{len(team_members[0])}\n{' '.join(map(str, team_members[0]))}\n{len(team_members[1])}\n{' '.join(map(str, team_members[1]))}")
solution.py