[백준] 16294 : Bee Problem (Python)

 

출처 : https://www.acmicpc.net/problem/16294

 

---

 

아이디어

'특정 셀에 꿀을 흘리면, 인접한 빈칸들에 퍼져나간다.'

해당 요구사항을 통해, 그래프 탐색 유형으로 해석 가능하며 DFS/BFS 모두 사용 가능하다. 주어지는 2차원 행렬은 공백이 포함되있기 때문에 다음의 사진을 바탕으로, 행렬의 범위와 탐색 방향을 계산할 수 있다.

 

한 번의 탐색은 빈칸들의 덩어리를 찾게 되므로, 한 덩어리(그룹)의 빈칸 개수를 찾아내고 이 수를 이용하여, 벌의 최소 작업량을 구할 수 있다.

 

정답 코드

# https://www.acmicpc.net/problem/16294
# Bee Problem
# 그래프탐색,BFS,DFS

input=__import__('sys').stdin.readline
deque=__import__('collections').deque

def bfs(sx,sy):
    q=deque([(sx,sy)])
    visited.add((sx,sy))
    cnt=1
    
    while q:
        x,y=q.popleft()
        for k in range(6):
            nx,ny=x+dx[k],y+dy[k]
            if 0<=nx<n and 0<=ny<2*m-1+(nx%2):
                if board[nx][ny]=='.' and (nx,ny) not in visited:
                    visited.add((nx,ny))
                    cnt+=1
                    q.append((nx,ny))
    
    return cnt

h,n,m=map(int,input().split())
board=[[*input()[:-1]] for _ in range(n)]
visited=set()
dx=[0,0,1,1,-1,-1]
dy=[2,-2,1,-1,1,-1]

if h==0:
    print(0)
    exit(0)

group=[] # 각 덩어리의 빈칸 개수를 저장하기 위한 배열
answer=0
for i in range(n):
    for j in range(i%2,2*m-1+(i%2),2):
        if (i,j) not in visited and board[i][j]=='.':
            cnt=bfs(i,j)
            group.append(cnt)

# 내림차순을 통해, 가장 많은 빈칸의 수를 가진 덩어리부터 꿀 작업 시작
for i in sorted(group)[::-1]:
    answer+=1
    if h<=0 or i>=h:
        break
    h-=i
print(answer)