[백준] 2638 - 치즈

https://www.acmicpc.net/status?user_id=imagen33&problem_id=2638&from_mine=1 

채점 현황

문제 한줄 이해

- 격자에 치즈와 공기로 채워져 있을 때 치즈가 2변 이상이 공기와 맞닿아(단 치즈로 둘러쌓인 공기는 영향을 주지 않는다) 있으면 한시간마다 녹아서 없어져 버린다고 한다.

이때 총 몇시간이 지나야 다 녹는지 구하기!

생각난 풀이

1번째 방법: 문제를 읽고 생각난 필요한 조건들

1. 우선 각 치즈에 공기에 맞닿는 부분이 몇변인지 세기

-> 먼저 BFS로 0,0부터 탐색을 시작한다 why? 문제에서 가장자리는 무조건 공기라고 주어졌다. 이때 0,0부터 탐색을 진행해 공기일때만 탐색 대상으로 삼으면 치즈로 둘러쌓인 내부는 탐색 대상에 포함시키지 않을 수 있다. (미로 찾기라 생각하자 벽으로 둘러쌓인 지역은 못가지 않는가!) 

2. 치즈를 어떻게 녹여야 하는지 -> 먼저 각 치즈들의 변의 갯수를 담을 배열을 선언해주고 탐색이 끝난 다음 2변 이상 맞닿아 있는 곳을 녹여준다.

 

import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
graph =[]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))
ans = 0

def dfs(x,y):
    que = deque()
    que.append((x,y))
    #방문처리
    cntvisited = [[0 for i in range(m)] for i in range(n)] 
    #각 치즈들의 몇변이 공기와 맞닿아있는지 
    visited = [[False for i in range(m)] for i in range(n)]
    while que:
        nowx,nowy = que.popleft()
        
        for i in range(4):
            nextx = nowx + dx[i]
            nexty = nowy + dy[i]
            
            if nextx >= 0 and nexty >=0 and nextx < n and nexty<m:
                if graph[nextx][nexty] == 0 and visited[nextx][nexty] == False:
                    visited[nextx][nexty] = True
                    que.append((nextx,nexty))
                # 공기와 맞닿을 경우 +1
                elif graph[nextx][nexty] == 1 and visited[nextx][nexty] == False:
                    cntvisited[nextx][nexty] += 1
    #맞닿은 변이 2개이상일 경우 녹여야 하기때문에 좌표 담아서 녹이기
    fire =[]
    for i in range(n):
        for j in range(m):
            if cntvisited[i][j] >=2:
                fire.append((i,j))
                
    for a,b in fire:
        graph[a][b] = 0
        
while True:
    cnt = 0

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                cnt +=1
    if cnt == 0:
        break
    ans +=1
    dfs(0,0)
print(ans)