[알고리즘][Python] 백준(BOJ) 2638 치즈_파이썬

 

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

2638번: 치즈

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 구현, 그래프 탐색, 너비 우선 탐색, 시뮬레이션

 

 

 

 

 

 

 

풀이 

<내용>

• n, m과 모눈종이 위의 치즈를 입력받는다.
• 치즈가 모두 녹아 없어졌는지 확인하기 위한 check 함수를 만든다.
  • 이중 for문을 통해 치즈가 있다면 False를 return
  • 치즈가 없다면 True를 return
• 치즈의 4변 중에서 적어도 2변 이상 실내온도의 공기와 접촉해야 치즈가 녹아 없어지므로 실내온도의 공기와 몇 개의 변이 접촉했는지 확인하기 위해 dfs 함수를 만든다.
  • 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않은 것이고 맨 가장자리에는 치즈가 놓이지 않기 때문에 (0, 0)을 기준으로 치즈가 없는 모든 곳을 다니며 주위에 치즈가 있다면 +1을 해서 접촉 횟수를 저장한다.
  • 치즈는 1로 표시되므로 2변 이상 접촉했다면 3 이상으로 표시된다.
• 2변 이상 접촉했을 경우 치즈를 녹아 없애야 하므로 remove_cheese 함수를 만들어 확인하고 치즈를 녹인다.
  • 이중 for문을 돌면서 치즈가 2변 이상 접촉했다면(3 이상) 치즈를 녹이고(0) 치즈가 2변 이상 접촉하지 않았다면(1 이상 2 이하) 치즈 기본값(1)으로 만든다.

 

 

 

<코드>

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int, input().split())
cheese = [list(map(int, input().split())) for _ in range(n)]

def check(cheese, n, m):
    for i in range(n):
        for j in range(m):
            if cheese[i][j] == 1:
                return False
    return True

def dfs(cheese, n, m, i, j):
    for k in range(4):
        x, y = i+dx[k], j+dy[k]
        if 0 <= x < n and 0 <= y < m and not visit[x][y]:
            if cheese[x][y] != 0:
                cheese[x][y] += 1
            else:
                visit[x][y] = 1
                dfs(cheese, n, m, x, y)
    
def remove_cheese(cheese, n, m):
    for i in range(n):
        for j in range(m):
            if cheese[i][j] >= 3:
                cheese[i][j] = 0
            elif cheese[i][j] > 0:
                cheese[i][j] = 1
    return cheese

res = 0
while True:
    if check(cheese, n, m):
        print(res)
        break
        
    visit = [[0 for _ in range(m)] for _ in range(n)]
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visit[0][0] = 1
    dfs(cheese, n, m, 0, 0)
    cheese = remove_cheese(cheese, n, m)
    res += 1