[백준] 2638 - 치즈 (Python)

문제 링크

알고리즘

• 구현
• 그래프 탐색

Tip

• 치즈와 치즈의 안 공기는 서로 접촉해도 녹지 않으므로 바깥 공기와 따로 구분할 수 있는 로직을 적용한다.

CHEESE = 1 # 치즈
OUTER_AIR = 2 # 바깥 공기
INNER_AIR = 0 # 안 공기

풀이

1. 입력을 이차원 리스트로 변환한다.

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())

paper = [list(map(int, input().split())) for _ in range(N)]

2. 치즈의 바깥 공기를 모두 숫자 2로 변경한다. 안쪽 공기와 구별하기 위함 ( BFS로 구현했다. )

direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]

queue = deque()
queue.append([0, 0])

while queue:
    i, j = queue.popleft()
    if paper[i][j] != 0:
        continue
    paper[i][j] = OUTER_AIR # 바깥 공기 모두 2로 변경
    for d in direction:
        next_i, next_j = i + d[0], j + d[1]
        if 0 <= next_i < N and 0 <= next_j < M and paper[next_i][next_j] == 0:
            queue.append([next_i, next_j])

3. 치즈의 위치(i,j)를 모두 큐에 저장한다.

cheeses = deque()

# 치즈 위치 찾기
for i in range(N):
    for j in range(M):
        if paper[i][j] == CHEESE:
            cheeses.append((i, j))

4. 큐에서 치즈를 하나씩 꺼내고 녹는지 검사한다. (바깥 공기와 두 면 이상 접촉하는지)

녹는 치즈는 melting 리스트에, 아닌 치즈는 다시 큐에 넣는다.

melting 리스트를 순회하면서, 녹는 치즈를 모두 2(바깥 공기)로 변경한다.

이 때 치즈가 녹으면 연결된 공기는 모두 바깥 공기에 오염된다.

따라서 녹는 치즈의 상하좌우 중에 0(안쪽 공기)가 있다면 BFS를 실행해서 연결된 안쪽 공기 모두 2(바깥 공기)로 변경한다.

한 턴(한 시간)이 끝나면 결과에 1을 추가한다.

마지막에 결과를 출력하면 끝.

while cheeses:
    melting = []
    for _ in range(len(cheeses)):
        cheese = cheeses.popleft()

        # 치즈가 녹는지 검사
        if is_melting(*cheese):
            melting.append(cheese)
        else:
            cheeses.append(cheese)

    for c in melting:
        paper[c[0]][c[1]] = OUTER_AIR
        for d in direction:
            ny, nx = c[0] + d[0], c[1] + d[1]
            if paper[ny][nx] == INNER_AIR:

                # 오염된 안쪽 공기를 모두 바깥 공기로 변환 (BFS)
                change_inner_air_to_outer_air(ny, nx)
	
    # 결과에 1 추가
    res += 1

# 모든 치즈가 다 녹으면 결과 출력
print(res)

# 치즈가 녹는지 검사하는 함수 - 상하좌우 중에 두 면이 바깥 공기(0)인지
def is_melting(i, j):
    cnt = 0
    for d in direction:
        if paper[i + d[0]][j + d[1]] == OUTER_AIR:
            cnt += 1
    if cnt >= 2:
        return True
    return False

# 오염된 안쪽 공기를 모두 바깥 공기로 변환하는 함수 (BFS)
def change_inner_air_to_outer_air(y, x):
    queue = deque()
    queue.append([y, x])
    while queue:
        i, j = queue.popleft()
        if paper[i][j] != INNER_AIR:
            continue
        paper[i][j] = OUTER_AIR
        for d in direction:
            ny, nx = i + d[0], j + d[1]
            if paper[ny][nx] == INNER_AIR:
                queue.append([ny, nx])

전체 코드

import sys
from collections import deque

input = sys.stdin.readline

CHEESE = 1
OUTER_AIR = 2
INNER_AIR = 0


# 치즈가 녹는지 검사하는 함수 - 상하좌우 중에 두 면이 바깥 공기(0)인지
def is_melting(i, j):
    cnt = 0
    for d in direction:
        if paper[i + d[0]][j + d[1]] == OUTER_AIR:
            cnt += 1
    if cnt >= 2:
        return True
    return False

# 오염된 안쪽 공기를 모두 바깥 공기로 변환하는 함수 (BFS)
def change_inner_air_to_outer_air(y, x):
    queue = deque()
    queue.append([y, x])
    while queue:
        i, j = queue.popleft()
        if paper[i][j] != INNER_AIR:
            continue
        paper[i][j] = OUTER_AIR
        for d in direction:
            ny, nx = i + d[0], j + d[1]
            if paper[ny][nx] == INNER_AIR:
                queue.append([ny, nx])


N, M = map(int, input().split())

paper = [list(map(int, input().split())) for _ in range(N)]


direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]


# 둘러쌓인 곳 찾기
# 처음에 바깥의 공기 모두 2로 변경
queue = deque()
queue.append([0, 0])
while queue:
    i, j = queue.popleft()
    if paper[i][j] != 0:
        continue
    paper[i][j] = OUTER_AIR
    for d in direction:
        next_i, next_j = i + d[0], j + d[1]
        if 0 <= next_i < N and 0 <= next_j < M and paper[next_i][next_j] == 0:
            queue.append([next_i, next_j])


cheeses = deque()


# 치즈 위치 찾기
for i in range(N):
    for j in range(M):
        if paper[i][j] == CHEESE:
            cheeses.append((i, j))

res = 0

while cheeses:
    melting = []
    for _ in range(len(cheeses)):
        cheese = cheeses.popleft()

        # 치즈가 녹는지 검사
        if is_melting(*cheese):
            melting.append(cheese)
        else:
            cheeses.append(cheese)

    for c in melting:
        paper[c[0]][c[1]] = OUTER_AIR
        for d in direction:
            ny, nx = c[0] + d[0], c[1] + d[1]
            if paper[ny][nx] == INNER_AIR:
                # 오염된 안쪽 공기를 모두 바깥 공기로 변환 (BFS)
                change_inner_air_to_outer_air(ny, nx)

    res += 1
    

print(res)