[Gold III]
https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
풀이
"두 변 이상 치즈 외부 공기와 접촉" 한다는 조건만 잘 처리해 준다면,
N, M (5 ≤ N, M ≤ 100) 이기 때문에 나머지는 Brute-Force로 처리해도 해결되는 문제이다.
air 2차원 배열을 생성하여, 모든 칸을 순회하며, 외부 공기와 접촉한 공기 칸을 체크한다.
이 때, air 배열의 모든 칸은 1로 초기화하고, 외부와 닿아 있는 공기 칸일 시,
그 칸부터 BFS를 통해, 이어진 모든 공기 칸을 air 배열에 체크한다.
그 이후는, 그저 모든 칸을 순회하며, 주위 4칸 중 air 배열에 체크된 칸(외부 공기와 통하는 공기 칸)이 2개 이상인 지 확인하고,
그렇다면 치즈를 녹여주면 된다.
이 과정을 계속 반복하여, 모든 치즈를 녹일 때까지 반복하면 성공.
자세한 흐름을 주석을 참조.
AC.
from collections import deque
N, M = map(int, input().split())
p = []
for _ in range(N):
p.append(list(map(int, input().split())))
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
air = [[1]*M for _ in range(N)]
def BFS(r, c):
deq = deque([(r, c)])
while deq:
nr, nc = deq.popleft()
for i in range(4):
lr = nr+dr[i]
lc = nc+dc[i]
# 격자 벗어남 체크 / 공기 칸인지 체크 / bfs에서 이미 지나간 칸인 지 확인 (air[lr][lc])
if 0 <= lr < N and 0 <= lc < M and p[lr][lc] == 0 and air[lr][lc] == 1:
air[lr][lc] = 0
deq.append((lr, lc))
T = 0 # 걸린 시간
while True:
T += 1
air = [[1]*M for _ in range(N)]
# 공기가 확산되는 칸을 check.
for r in range(N):
for c in range(M):
# 치즈가 있는 칸이거나, 이미 외부 공기와 통한다고 체크한 칸은 pass.
if p[r][c] == 1 or air[r][c] == 0:
continue
# 현재 칸이 외부와 닿아 있으면 isAirExposed = True.
isAirExposed = False
for i in range(4):
lr = r+dr[i]
lc = c+dc[i]
if lr < 0 or lr >= N or lc < 0 or lc >= M:
isAirExposed = True
break
# 외부와 맞닿은 칸부터 BFS로 공기인 칸을 탐색하며 외부 공기와 통하는 것으로 check (0으로 변경)
if isAirExposed:
BFS(r, c)
# 치즈 녹이기
for r in range(N):
for c in range(M):
if p[r][c] == 0:
continue
cnt = 0
for i in range(4):
lr = r+dr[i]
lc = c+dc[i]
if air[lr][lc] == 0:
cnt += 1
# 외부 공기와 2변 이상 닿으면, 치즈를 녹인다.
if cnt >= 2:
p[r][c] = 0
# 다 녹음 체크
isAllMelt = True
for r in range(N):
if not isAllMelt:
break
for c in range(M):
if p[r][c] == 1:
isAllMelt = False
break
if isAllMelt:
print(T)
break