[백준 / Python] 32031번 석고 모형 만들기

문제

https://www.acmicpc.net/problem/32031

---

코드

 

import sys
input = sys.stdin.readline

r, c = map(int, input().split())

parent = [i for i in range(r * c * 8)]
union_size = [1 for _ in range(r * c * 8)]

def find(a):
    if parent[a] == a:
        return a
    parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return
    
    if union_size[a] < union_size[b]:
        parent[a] = b
        union_size[b] += union_size[a]
    else:
        parent[b] = a
        union_size[a] += union_size[b]

for i in range(r):
    data = input()
    for j in range(c):
        temp = 8 * i * c + 8 * j 
        if data[j] == 'I':
            union(temp + 0, temp + 2)
            union(temp + 1, temp + 3)
            union(temp + 4, temp + 6)
            union(temp + 5, temp + 7)
        if data[j] == 'H':
            union(temp + 0, temp + 1)
            union(temp + 2, temp + 3)
            union(temp + 4, temp + 5)
            union(temp + 6, temp + 7)
        if data[j] == 'O':
            union(temp + 0, temp + 4)
            union(temp + 1, temp + 5)
            union(temp + 2, temp + 6)
            union(temp + 3, temp + 7)

for i in range(r - 1): # 세로끼리 연결
    for j in range(c):
        temp = 8 * i * c + 8 * j
        union(temp + 2, temp + 8 * c + 0)
        union(temp + 3, temp + 8 * c + 1)
        union(temp + 6, temp + 8 * c + 4)
        union(temp + 7, temp + 8 * c + 5)
        
for i in range(r): 
    for j in range(c - 1): 
        temp = 8 * i * c + 8 * j
        union(temp + 1, temp + 8 + 0)
        union(temp + 3, temp + 8 + 2)
        union(temp + 5, temp + 8 + 4)
        union(temp + 7, temp + 8 + 6)

parent_set = set(find(i) for i in range(len(parent)))
print(len(parent_set))

1x1 석고가 8개의 점을 가지고 있다고 할때 세로로 원통을 뚫으면 세로로 내부 위 아래 점이 연결되고 가로로 원통을 뚫으면 가로로 점이 연결된다고 생각하면 이해하기 쉽습니다

이런느낌으로..?

 

이리고 각 1x1 석고가 마주치는 점을 모두 단순히 연결하고 점 그룹( 연결이 된 점들을 한개의 그룹으로 봄)의 개수를 세면 되는 문제입니다. 

 

따라서 유니온 파인드로 쉽게 풀 수 있습니다. 

아니면 bfs 사용해도 되고..