[백준2638/골드3] 치즈 - Python

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

 

백준 2637 빙산 문제 처럼 몇번 닿았는지 카운트하고 조건에 만족했을 때 (2번 이상 닿았을때) 치즈를 녹이는 과정을 반복하려고 했다.

 

 

1. 무조건 외부 공기인 (0, 0)부터 덱에 넣어 외부 공기 탐색하며 외부 공기 표시(-1) 하기

2. 외부 공기 탐색 도중 치즈 (1)이 나오면 해당 구역 visited에 += 1

3. bfs 전부 탐색 후, visited가 2 이상인 부분 (외부공기가 두번 이상 닿은 부분) 치즈 녹이기

4. 치즈가 전부 녹을 때 까지 (녹이는 치즈가 없을 때 까지) 반복

 

# 성공 코드 1

# python 34976 KB 1176 ms

from collections import deque

N, M = map(int, input().split()) # 세로, 가로
mp = [list(map(int, input().split())) for _ in range(N)]
result = 0
all_melt = False

# 외부 공기에 닿은 치즈 녹이기
while not all_melt:
    q = deque([(0, 0)])
    visited = [[0] * M for _ in range(N)]
    visited[0][0] = -1
	
    # 외부 공기가 나오면 외부공기 체크(-1)하고, 치즈가 나오면 방문표시 (+= 1)
    while q:
        i, j = q.popleft()

        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M and visited[ni][nj] == 0 and mp[ni][nj] == 0:
                visited[ni][nj] = -1
                q.append((ni, nj))
            elif 0 <= ni < N and 0 <= nj < M and mp[ni][nj] == 1:
                visited[ni][nj] += 1

    melted = False # 녹은 치즈가 있는지 체크
    
	# 두번 이상 방문한 치즈 녹이기
    for i in range(N):
        for j in range(M):
            if visited[i][j] >= 2:
                mp[i][j] = 0
                melted = True
	
    # 녹은 부분이 없으면 모든 치즈가 다 녹음
    if not melted:
        all_melt = True
	
    # 녹은부분 있으면 한시간 추가
    else:
        result += 1

print(result)

 

이렇게 하니까 되게 오래걸렸다.

그래서 방문 횟수만 추가하는게 아니라, 백준 2637 빙산 처럼 녹은 치즈를 배열로 관리하면서 체크하고 함수화했다.

 

 

1. 외부 공기 체크하는 함수 outside()

1-1. 배열에 치즈가 아니면 (!= 1) 외부공기 처리 후 덱에 추가

2. 치즈 녹이는 함수 melting()

2-1. 전체 배열을 순회하며 치즈인 부분이고, 주변에 외부공기가 (-1) 두번 이상이면 녹을 치즈 배열에 추가

2-2. 녹을 치즈 배열이 없으면 False return

2-3. 녹을 치즈 배열이 있으면 녹인 후 True return

3. 치즈가 전부 녹을 떄 까지 (melting 함수의 반환값이 False일 때 까지) 반복

 

# 성공 코드 2

# python 35000 KB 568 ms

from collections import deque

N, M = map(int, input().split()) # 세로, 가로
mp = [list(map(int, input().split())) for _ in range(N)]

# 외부 공기에 닿은 치즈 녹이기
def outside():
    visited = [[False] * M for _ in range(N)]
    visited[0][0] = True
    mp[0][0] = -1
    q = deque([(0, 0)])

    while q:
        i, j = q.popleft()

        for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            ni, nj = i + di, j + dj

            if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj] and mp[ni][nj] != 1:
                mp[ni][nj] = -1
                q.append((ni, nj))
                visited[ni][nj] = True

def melting():

    melting_cheese = []

    for i in range(N):
        for j in range(M):
            if mp[i][j] == 1:
                cnt = 0

                for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    ni, nj = i + di, j + dj

                    if 0 <= ni < N and 0 <= nj < M and mp[ni][nj] == -1:
                        cnt += 1

                if cnt >= 2:
                    melting_cheese.append((i, j))

    if not melting_cheese:
        return False

    for x, y in melting_cheese:
        mp[x][y] = 0

    return True

result = 0

while True:
    outside()
    if not melting():
        break
    result += 1

print(result)