PS Featured

[PS] BOJ 33915 / 불꽃놀이의 아름다움 2

Minjun Kim

21 Dec 2025 • 2 min read

Thumbnail: Photo by zuzanka galczynska (Unsplash)

문제 링크: https://www.acmicpc.net/problem/33915

풀이

그래프 색칠하기

인접한 두 정점끼리 서로 다른 색으로 칠하는 규칙을 따라 전체 그래프를 칠하는 문제입니다. 이는 이분 그래프의 개념을 활용해 접근할 수 있습니다.
다만, 이분 그래프처럼 그래프의 정점이 온전히 2개의 그룹으로만 분리되지는 않습니다. 따라서 그래프 탐색 과정에서 적절히 색의 개수를 늘려가며 구분해줘야 합니다.

현재 그래프에 존재하는 색상의 개수를 $C$라 할 때, 이전에 방문한 정점의 색상을 $P$라고 한다면 현재 정점은 $(P + 1) \mod C$로 계산했습니다.
만약 현재 정점이 이미 색칠된 상태이며 이전 정점과 같은 색상으로 칠해져 있다면, $C$를 1 증가시키고 새로운 색상으로 칠해줬습니다.

전체 코드

from collections import deque
input = open(0).readline
N = int(input())
edges = tuple([] for _ in range(N + 1))

for _ in range(N):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

# BFS
color = [-1 for _ in range(N + 1)]
queue = deque([1])
color_cnt = 2 # 최소한 2개의 색상은 필요하다.
color[1] = 0

while queue:
    pos = queue.popleft()

    for other in edges[pos]:
        if color[other] == -1: # 방문하지 않은 경우
            color[other] = (color[pos] + 1) % color_cnt
            queue.append(other)
        elif color[other] == color[pos]: # 색상 중복 시 색상의 가짓수를 늘리고 새로운 색상으로 칠해준다.
            color[other] = color_cnt
            color_cnt += 1

print(color_cnt)

solution.py

풀이

​그래프 색칠하기

전체 코드

그래프 색칠하기