[백준] 2638 치즈 - Python

** 백준 문제를 solution 타입 문제로 변형한 풀이입니다. **

2638번: 치즈

POINT

내부와 외부 공간 분리하기

• 백준의 <그림 2>처럼 치즈가 외부에 노출되어도 다른 치즈 안에 있으면 녹지 않는다.
• 내부가 아닌 외부 공간에 두 곳 이상이 노출되면, 그 치즈는 1시간 뒤 녹는다.
• 치즈를 녹인 후 다시 내부와 외부를 분리해야 한다.

치즈 한번에 녹이기

• 1시간 뒤 녹는 치즈를 찾자마자 바로 녹이면 안된다. 그 치즈가 녹고 외부에 노출되는 치즈가 있다면 잘못 녹일 수 있다.
• 모든 치즈를 탐색한 후 동시에 녹여야 한다.
• 동시에 치즈를 녹인 후 시간을 증가시킨다.

풀이

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 외부 공간 표시
def dfs(x, y, graph):
	if x < 0 or x >= n or y < 0 or y >= m or graph[x][y] != 0:
		return
	graph[x][y] = -1 # 외부 공간

	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		dfs(nx, ny, graph)

# 1시간 뒤 녹는 치즈 찾기
def findMelting(graph):
  melting = []
  
  for i in range(1, n-1):
    for j in range(1, m-1):
      if graph[i][j] == 1:
        count = 0
        
        for k in range(4):
          nx = i + dx[k]
          ny = j + dy[k]
          if graph[nx][ny] == -1: count += 1
        
        # 상, 하, 좌, 우 중 두 곳 이상이 0이면 녹는 치즈
        if count >= 2:
          melting.append((i, j))
    
  return melting

def meltCheese(melting, graph):
  for x, y in melting:
    graph[x][y] = 0

def solution(n, m, input_board):
	answer = 0

	# 내부, 외부 구분
	dfs(0, 0, input_board)
	# 1시간 뒤 녹을 치즈
	meltingCheeses = findMelting(input_board)

	# 치즈가 다 녹을 때까지 반복
	while meltingCheeses:
		meltCheese(meltingCheeses, input_board)
		answer += 1

		# 치즈가 있던 자리(0)에서 다시 내부, 외부 구분
		for x, y in meltingCheeses:
			dfs(x, y, input_board)

		meltingCheeses = findMelting(input_board)

	return answer