백준 2638 치즈 파이썬

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

 

 

6개월 전에 처음 풀었던 문제다. 그 때는 1트만에 해결했는데, 이번에 다시 풀어보니 15트를 했다. 문제를 너무 어렵게 생각했던 것이 문제였다.​

이 문제의 핵심은 공기가 내부인지 외부인지를 판단하는 로직이다. 처음 접근했을 때, 이 컨디션을 정의하기 위해 'BFS로 탐색한 공기의 갯수 < 둘러싼 치즈의 갯수'인 경우 모두 내부 공기로 설정을 했다. 이렇게 했을 때, 체크하지 못한 경우의 수가 너무 많았다. 가장 대표적인 것은 0,0부터 시작해서 삥 둘렀는데 치즈와 맞닿은 공기보다 치즈가 더 많은 경우가 존재한다는 것이다.

​

위 경우가 대표적이다. 0,0부터 시작해서 삥 둘렀는데 모든 공기는 외부 공기다. 그런데 0과 접촉하는 1의 갯수가 0보다 많기 때문에 내가 만든 논리에서는 반례가 존재할 수 밖에 없다. 조건을 설정했으면, 그 조건이 타당한지를 항상 다시 한번 검토를 해야하는 것 같다.

​​그래서 기존 논리를 가져가면서, 바깥쪽의 공기를 먼저 다 제거해버리고 시작해보기로 했다. 바깥쪽의 공기를 다 시작하고, 나머지 체크하지 못한 공기를 체크하면 위 반례를 제외할 수 있기 때문이다. 위 반례를 클리어하면서 문제는 맞았다. 그런데 다시 한번 든 생각이 하나 있다.

​

"이미 외부 공기를 다 제거했는데, 내가 만든 로직으로 다시 체크할 필요가 있나? 없는데? "

​

맞다. 없었다. 삽질을 한거다. 빼니까 좀 더 실행속도가 빨라졌다. 

​

문제를 이렇게 간단하게 풀 수 있는 이유는 오직 하나다.

치즈가 가장 자리에 절대로 존재하지 않는다는 조건이 주어졌기 때문이다. 따라서 0,0에는 반드시 공기가 있고, 이 공기는 반드시 외부공기다. 그리고 이 공기와 연결되는 것들만이 모두 외부공기고 나머지는 내부 공기다. 만약에 이 조건이 없다면, 내가 만든 로직을 잘 사용해보는 것이 맞을 것 같다.

 

import sys
from collections import deque


# 외곽 부분에서 시작되는 공기를 모두 2로 처리해준다.
def remove_outer_air(n,m, check_map, my_map):
    que = deque()
    que.append((0,0))
    check_map[0][0] = 2

    while que :
        r,c   = que.popleft()
        for rr, cc in tra_list:
            next_r, next_c = r + rr , c + cc
            if -1 < next_r < n and -1 < next_c < m:
                if my_map[next_r][next_c] == 0 and check_map[next_r][next_c] == 0 :
                    check_map[next_r][next_c] = 2
                    que.append((next_r, next_c))
    return check_map

def find_inner_space(n, m, check_map, my_map):

    visit_map = createMap(n, m)

    for r in range(n):
        for c in range(m):
            #공기 + 방문한 적이 없을 때 탐색한다.
            if my_map[r][c] == 0 and check_map[r][c] == 0 and visit_map[r][c] == 0 :

                que = deque()
                inner, cheese = 1,0
                que.append((r,c))
                stack = [(r,c)]
                cheese = set()

                while que :
                    rr,cc = que.popleft()

                    for rrr,ccc in tra_list:
                        next_r,next_c = rr + rrr, cc + ccc
                        # 맵 안에 있을 때
                        if -1 < next_r < n and -1 < next_c < m  :
                            # 치즈 일 경우
                            # 치즈는 다른 사람들이 체크를 해야하기 때문에 집합으로 중복 제거한다.
                            if (next_r, next_c) not in cheese and my_map[next_r][next_c] == 1:
                                cheese.add((next_r, next_c))


                            #방문한 적 없고, 공기일 경우
                            #방문한 적이 없고, 공기면 아니면 카운트 올리고 que에 넣는다.
                            elif check_map[next_r][next_c] == 0 and my_map[next_r][next_c] == 0 and visit_map[next_r][next_c] == 0  :

                                inner +=1
                                que.append((next_r, next_c))
                                stack.append((next_r, next_c))
                                visit_map[next_r][next_c] = 1


                # 치즈가 더 많은 경우, 반드시 내부다.
                if inner < len(cheese):
                    while stack :

                        rrrr,cccc = stack.pop()
                        check_map[rrrr][cccc] = 1


def check_remove(n,m,check_map, my_map):

    stack = []
    for r in range(n):
        for c in range(m):

            #치즈면 확인
            if my_map[r][c] == 1:
                # 초기값 셋팅
                cnt = 0
                # 4방향을 확인한다.
                for rr,cc in tra_list:
                    next_r, next_c = r + rr, c + cc
                    if -1 < next_r < n and -1 < next_c < m:
                        # 공기 + 외부인지 확인한다 ( check_map == 1이면 내부공기다 )
                        if my_map[next_r][next_c] == 0 and check_map[next_r][next_c] == 2:
                            # 공기 + 외부가 맞으면, 카운트 하나 늘려준다
                            cnt +=1

                # 2변 이상 접촉 했으면, 제거될 치즈로 넣어준다.
                if cnt >= 2 :
                    stack.append((r,c))

    # 제거될 치즈가 없음
    if len(stack) == 0 :
        return True

    # 제거될 치즈가 있음.
    else :
        while stack:
            # 치즈를 모두 제거해준다.
            r, c = stack.pop()
            my_map[r][c] = 0
        return False



tra_list = [[1,0],[0,1],[-1,0],[0,-1]]


def createMap(n,m):
    return [[0 for _ in range(m)] for _ in range(n)]


n,m = map(int,sys.stdin.readline().split())
my_map = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]



ans = 0
while 1:

    # 내/외부 공기 체크용 맵 생성
    check_map = createMap(n, m)

    # 외부 공기 삭제
    check_map = remove_outer_air(n,m , check_map, my_map)

    # 내부 공기인지 확인함.
    find_inner_space(n, m, check_map, my_map)

    # 내부 공기정보 넣어주고, 치즈 삭제함.
    remove_none = check_remove(n, m, check_map, my_map)

    # 만약 제거된 것이 없다면 종료한다.
    if remove_none:
        print(ans)
        break

    # 제거된 것이 있다면 시간을 눌려준다.
    ans +=1

​