[백준] 2638번 : 치즈

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

2638번: 치즈

위의 문제는 탐색의 문제로 깊이우선탐색과 너비우선 탐색으로 모두 문제를 해결 할 수 있습니다.

1. 치즈의 개수를 구한다. 개수가 0이상이라면 치즈를 녹여야 한다. 그렇지 않으면 종료한다.

2. 치즈를 녹일때 너비우선탐색 혹은 깊이우선탐색으로 녹여야할 치즈 후보를 구한다.

3. 녹여야할 치즈 후보를 현재 그래프에 적용하고, 시간을 증가한다.

4. 1~3까지 계속 반복하여 시간 최종 시간값을 구한다.

 

1. 깊이우선탐색 문제 접근

- 깊이우선탐색으로 접근하려면 (0,0) 부터 탐색을 시작한다. ( 맨 바깥쪽에 있는 (0,0)은 무조건 외부 공기이다 )

- 외부공기만 깊이우선탐색하고 만약 외부공기에서 치즈가 탐색된다면 가중치를 증가시킨다.

- 외부공기를 깊이우선탐색할때 재방문 하지 않도록 Visited처리를 해준다.

 

from pprint import pprint
import sys
sys.setrecursionlimit(200000)
move = ((0,1), (0,-1), (1,0), (-1,0))
N, M = map(int, input().split()) # 세로, 가로
graph = []
for _ in range(N):
    arr = list(map(int ,input().split()))
    graph.append(arr)
    
def dfs(i,j, searchArea):
    searchArea[i][j] = 1
    for dy, dx in move:
        ny = dy + i
        nx = dx + j
        if N > ny >=0 and M > nx >=0:
            if graph[ny][nx] == 1: # 치즈이면
                searchArea[ny][nx] += 1
            else: # 외부공기이면
                if searchArea[ny][nx] == 0:
                    dfs(ny,nx, searchArea)
                
def getCheezeCount():
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1: # 치즈가 하나라도 있으면 False 리턴
                return True
    
    return False
    
    
time = 0
while(getCheezeCount()): # 치즈가 다 녹아 없어질때까지
    time += 1
    searchArea = [[0 for _ in range(M)] for _ in range(N)] # 외부공기 가중치값 저장 배열
    dfs(0,0, searchArea)
                        
    for i in range(N):
        for j in range(M):
            if searchArea[i][j] >= 2: # 외부공기 가중치가 2보다 클경우 없앤다.
                graph[i][j] = 0
                
print(time)

 

2. 너비우선탐색 문제 접근

- 너비우선탐색도 마찬가지로 (0,0) 부터 탐색을 시작한다.

- 외부공기만 너비우선탐색하고 만약 외부공기에서 치즈가 탐색된다면 가중치를 증가시킨다.

- 외부공기를 너비우선탐색할때 재방문 하지 않도록 Visited처리를 해준다.

from collections import deque
from pprint import pprint

move = ((0,1), (0,-1), (1,0), (-1,0))
N, M = map(int, input().split()) # 세로, 가로
graph = []
for _ in range(N):
    arr = list(map(int ,input().split()))
    graph.append(arr)


def bfs(i,j):
    queue = deque()
    searchArea[i][j] = 1
    queue.append((i,j))
    while queue:
        y,x = queue.popleft()
        for dy, dx in move:
            ny = dy + y
            nx = dx + x
            if N > ny >=0 and M > nx >=0:
                if graph[ny][nx] == 1: # 치즈이면
                    searchArea[ny][nx] += 1
                else: # 외부공기이면
                    if searchArea[ny][nx] == 0:
                        searchArea[ny][nx] = 1
                        queue.append((ny,nx))
                        
def getCheezeCount():
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1: # 치즈가 하나라도 있으면 False 리턴
                return True
    
    return False

time = 0
while(getCheezeCount()): # 치즈가 다 녹아 없어질때까지
    time += 1
    searchArea = [[0 for _ in range(M)] for _ in range(N)] # 외부공기 가중치값 저장 배열
    bfs(0,0)     
    for i in range(N):
        for j in range(M):
            if searchArea[i][j] >= 2: # 외부공기 가중치가 2보다 클경우 없앤다.
                graph[i][j] = 0
    
print(time)