[백준] 치즈

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

2638번: 치즈

bfs를 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 치즈가 펼쳐져 있는 모눈종이가 주어지는데, 가장 바깥쪽 공기와 두면 이상 접촉해 있는 치즈는 한시간 만에 녹아 없어집니다. 이 때, 모든 치즈가 사라지는데 까지 걸리는 시간을 return 해야 합니다. 

(단, 치즈 내부에 있는 공기와 접촉한 것은 면 수에 포함하지 않습니다)

 

간단한 예시로 문제를 더 추가설명 해보면, 

다음과 같은 과정을 통해 치즈가 순차적으로 사라지게 됩니다.

 

<Solution>

이 문제는 내부의 공기와 접촉해 있는 것은 면 수에 포함되지 않는다는 조건 때문에 조금 까다로워집니다.

 

만약 이 조건이 없다면, 우리는 그냥 각각의 치즈들이 몇개의 면과 접촉해 있는지를 추적하며, 없애주면 문제를 간단하게 해결할 수 있습니다. 하지만 여기에서는 우리는 내부의 공기와 외부의 공기를 구분지어서 생각해야 합니다. 

 

그러기 위해서 외부의 공기를 마스킹 하는 작업을 bfs를 통해 진행합니다. [0,0]의 지점에서 출발해 bfs를 하면서 치즈가 아닌 부분들을 마스킹 하게 되면 가장 바깥쪽 공기와, 치즈 내부 공기를 다른 숫자로 마스킹할 수 있습니다. 

저 같은 경우에는 바깥 공기를 2로 마스킹 해주었습니다. 이렇게 마스킹이 끝난 이후에는 각각의 cheese를 search_set이라는 집합 자료구조에 저장해둡니다. 

search_set = set()
for i in range(N):
    for j in range(M):
        if array[i][j] == 1: # if cheese
            search_set.add((i,j))

그리고 이 search_set이 존재하는 동안, 각각의 cheese에 대해 다음과 같은 과정을 합니다.

1. 네 방향을 체크해서 2인 것(바깥공기)의 갯수가 2개 이상인 것이 나오는지 체크한다. 2. 만약 바깥 공기가 2개 이상이여서 사라지게 되면, 해당하는 부분을 2로(바깥공기) 바꿔주고, 만약 이어진 내부공기가 있다면 이 내부공기도 bfs를 통해 2(바깥공기)로 바꿔준다.

간단하게 그림으로 표현하면 다음과 같습니다. 

실제 구현입니다.

import sys
from collections import deque

def outofblock(row_size,column_size, row_index, column_index): # num row, num column index index
    return row_index<0 or row_index>row_size-1 or column_index<0 or column_index>column_size-1

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

array = []
for _ in range(N):
    array.append(list(map(int, sys.stdin.readline().rstrip().split())))

# print(array)

# right down up left
d_row = [0, 1, 0, -1]
d_column = [1, 0, -1, 0]

# mask out air(bfs)
visited = [[False] * M for _ in range(N)]
q = deque([[0,0]])

while(q):
    row, column = q.popleft()
    if visited[row][column]:
        continue
    array[row][column] = 2
    visited[row][column] = True
    for i in range(4):
        new_row = row + d_row[i]
        new_column = column + d_column[i]
        if not outofblock(N, M, new_row, new_column) and not visited[new_row][new_column] and array[new_row][new_column] == 0:
            q.append([new_row,new_column])

# print(array)
search_set = set()
for i in range(N):
    for j in range(M):
        if array[i][j] == 1: # if cheese
            search_set.add((i,j))

ans = 0
while(search_set):
    ans += 1
    remove_set = set()
    for cheese in search_set:
        counter = 0
        # check 4 direction
        for k in range(4):
            new_r = cheese[0] + d_row[k]
            new_c = cheese[1] + d_column[k]
            if array[new_r][new_c] == 2:
                counter+=1
        if counter >=2:
            remove_set.add(cheese)
    
    # calculate new air and array status
    for cheese in remove_set:
        # from this point bfs(make outer air)
        q = deque([[cheese[0],cheese[1]]])
        visited_ = [[False] * M for _ in range(N)]
        while(q):
            r,c = q.popleft()
            if visited[r][c]:
                continue
            array[r][c] = 2
            visited[r][c] = True
            # check four direction
            for i in range(4):
                new_row = r + d_row[i]
                new_column = c + d_column[i]
                if not outofblock(N, M, new_row, new_column) and not visited[new_row][new_column] and array[new_row][new_column] == 0:
                    q.append([new_row,new_column])

    search_set = search_set - remove_set

print(ans)

 

<추가>

한가지 언급할 부분은 내부 공기를 외부 공기로 변환시키는 bfs과정입니다. 이 과정에서 visited_ array를 두면, 백준 기준으로는 코드가 더 느려지게 됩니다. bfs과정에서 visited_ array를 두는 이유는 불필요한 중복을 줄이기 위해서 인데, visited_ array를 둔 1번 코드의 실행 속도가 더 느렸습니다. 이것은 조금 이상한 부분인데

 

N, M (5 ≤ N, M ≤ 100) 의 조건으로 생각보다 모눈종이의 사이즈가 크지 않아서 내부의 공기가 넓은 면적으로 주어지지 않아서가 아닐까 추측합니다. 

(실제로 궁금한 분들은 두 코드를 여러 환경에서 큰 테스트케이스(내부 공기가 엄청 큰 극단적인 case)를 만들고 돌려보면 될 듯 합니다)

 

(1번 코드)

    # calculate new air and array status
    for cheese in remove_set:
        # from this point bfs(make outer air)
        q = deque([[cheese[0],cheese[1]]])
        visited_ = [[False] * M for _ in range(N)]
        while(q):
            r,c = q.popleft()
            if visited[r][c]:
                continue
            array[r][c] = 2
            visited[r][c] = True
            # check four direction
            for i in range(4):
                new_row = r + d_row[i]
                new_column = c + d_column[i]
                if not outofblock(N, M, new_row, new_column) and not visited[new_row][new_column] and array[new_row][new_column] == 0:
                    q.append([new_row,new_column])

(2번 코드)

    # calculate new air and array status
    for cheese in remove_set:
        # from this point bfs(make outer air)
        q = deque([[cheese[0],cheese[1]]])
        while(q):
            r,c = q.popleft()
            array[r][c] = 2
            # check four direction
            for i in range(4):
                new_row = r + d_row[i]
                new_column = c + d_column[i]
                
                if not outofblock(N, M, new_row, new_column) and array[new_row][new_column] == 0:
                    q.append([new_row,new_column])