[백준] 2638 치즈(파이썬/python)

🎈문제

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

 

🎁알고리즘 및 접근

bfs

1. 외부공기와 내부공기를 판단을 먼저 해야 녹을 치즈인지 아닌지를 판단할 수 있었다. 

 따라서 다음과 같은 순서로 코드를 짜기로 했다.

 1) 외부공기 / 내부공기 판단

 2) 녹을 치즈 판단

 3) 하나라도 녹으면 시간 +1

2. 외부공기 / 내부공기 판단

 (0,0)은 가장자리이므로 무조건 외부공기이다. 따라서 (0,0)부터 bfs를 돌리면 "외부공기"와 "치즈&내부공기" 로 나뉜다.

3. 녹을 치즈 판단

 외부공기와 내부공기가 판단되면, 상하좌우를 살펴 외부공기가 2개 이상이면  치즈를 녹인다.

4. 반복

💻코드

# 2638 치즈

from collections import deque

def Check(x,y):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    cnt = 0

    for i in range(4):  # 상하좌우 공기 체크
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
            continue
        if air_graph[nx][ny] == 1:    # 외부 공기이면 cnt + 1
            cnt += 1
    if cnt > 1: # 1시간 뒤 녹을 치즈면
        graph[x][y] = 0 # 치즈 녹이기
        return True
    return False



# 외부 공기 전부 1로 표시
def Air():
    deq = deque()
    deq.append([0,0])
    air_graph[0][0] = 1
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]

    while deq:
        x,y = deq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                continue
            if graph[nx][ny] == 0 and air_graph[nx][ny] == 0:
                air_graph[nx][ny] = 1
                deq.append([nx,ny])
    return
    


# 1. 입력 받기
n,m = map(int,input().split())

graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

time = 0
cheese = True

while cheese:   # 치즈가 녹을 때마다 외부/내부공기가 바뀜
    cheese = False
    air_graph = [[0 for j in range(m)] for i in range(n)] # 내부 / 외부 공기 판단
    Air()   # 가장자리는 외부공기니까 가장자리부터 bfs 돌려버리면 다 외부공기인 1로 채워짐
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:    # 치즈를 만나면
                if Check(i,j):   # 한 시간 뒤 녹을 치즈인지 판단하고 녹이기
                    cheese = True   # 치즈 하나라도 녹으면 True
    if cheese:  # 치즈가 하나라도 녹았으면
        time += 1   # 시간 추가

print(time)

🎄코드 설명

위의 코드와 주석으로 대체한다.