백준 2638번 파이썬 코드 답안

문제

N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

문제 풀이 (이 풀이는 최선의 방법이 아닐 수 있고, 내가 그냥 풀던 방법을 기록해둔 것임)

이 문제의 핵심은 치즈가 외부 공기와 나누어지는지를 구별하는 것이라고 생각한다. 치즈가 외부 공기와 나누어지는지만 알게 된다면, 나머지는 간단한 조건식을 통해서 모두 처리 해버릴 수 있기 때문이다. 그렇기 때문에 나는 치즈가 외부 공기와 나누어지는 조건이 무엇인지를 살펴보고자 했다. 

처음에는 치즈 주변의 공기갯수로 접근을 하려고 했으나, 이것으로 모든 경우의 수를 나눌 수 없었다. 예제에서 주어진 사진만 봐도 알 수 있다. 어떤 치즈는 주변에 접근한 공기가 2개가 있으나 외기에 실제로 노출된 것은 1개다. 반면에 또 다른 치즈는 접근한 공기가 2개 있는데, 이 모두 외기였다. 즉, 치즈 하나만 바라보고 그 주변을 살펴 보는 것으로는 치즈가 외기에 노출되었는지를 판별할 수 있는 근거가 부족하다.

따라서, 나는 처음 만나게 되는 대기 군집과 치즈 군집의 갯수를 비교하는 식으로 치즈가 이 공기가 치즈에 둘러싸여있는지를 확인하는 식으로 접근했다.

위의 그림에서 흰 셀은 공기이고 노란색은 치즈라고 볼 수 있다. 각 셀에 있는 숫자들은 그 군집들의 갯수를 하나하나씩 센 것이다. 공기는 각각 82개, 1개, 21개의 군집으로 이루어져 있고, 치즈는 각각 8, 24개의 군집으로 이루어져있다. 그림을 보면 알겠지만, 치즈로 공기가 둘러싸여있으면 공기는 결코 치즈보다 많을 수 없다. 따라서, 내가 치즈가 진공인지 아닌지를 판별한 공식은 이것 하나다

BFS로 확인한 치즈의 갯수 > 공기의 갯수  → 진공공간
BFS로 확인한 치즈의 갯수 <= 공기의 갯수 → 대기노출( = 등호가 들어가는 이유는 같은 공기면 결코 치즈가 다 감쌀 수 없음) 

따라서 해당 공식으로 치즈가 대기 노출인지, 진공공간인지 정확히 공간을 구별해준다. 그리고 처음 구해두었던 치즈의 좌표를 하나씩 꺼내오면서 4가지 방향을 살펴보았을 때, 대기노출된 'A'의 갯수가 2개 이상인지 측정하고, 2개 이상일 경우 해당 좌표는 사라지는 것으로 알고리즘을 짯다. 

코드는 지저분하지만 아래와 같다. 

import sys
from collections import deque

def bfs(br,bc) :
    global r
    global c
    que = deque()
    que.append((br,bc))
    v[br][bc] = 0
    while que :
        bbr,bbc = que.popleft()
        for kkk in tra_list :
            next_r = bbr + kkk[0]
            next_c = bbc + kkk[1]
            if 0 < next_r < r+1 and 0 < next_c < c+1 :
                if my_list[next_r][next_c] == 0 and v[next_r][next_c] == 0 :
                    que.append((next_r,next_c))
                    v_li.add((next_r,next_c))
                elif my_list[next_r][next_c] == 1 and v[next_r][next_c] == 0 :
                    c_li.add((next_r,next_c))
                v[next_r][next_c] = 1

def sol() :
    global r
    global c
    for i in range(1, r+1) :
        for j in range(1, c+1) :
            if v[i][j] == 0 and my_list[i][j] == 0 :
                bfs(i,j)
                if len(v_li) >= len(c_li) and len(c_li) != 0 :
                    for kkkk in range(len(v_li)) :
                        rrr,ccc = v_li.pop()
                        v[rrr][ccc] = 'A'
                elif len(v_li) < len(c_li) and len(v_li) != 0 :
                    for kkkk in range(len(v_li)) :
                        rrr,ccc = v_li.pop()
                        v[rrr][ccc] = 'B'
    if len(c_li) == 0 :
        return True
    while c_li :
        rrrrr,ccccc = c_li.pop()
        my_cnt = 0
        for kkkkk in tra_list :
            next_r = rrrrr + kkkkk[0]
            next_c = ccccc + kkkkk[1]
            if 0 < next_r < r+1 and 0 < next_c < c+1 :
                if v[next_r][next_c] == 'A' :
                    my_cnt +=1
        if my_cnt >= 2 :
            my_list[rrrrr][ccccc] = 0
    return False


tra_list = [[1,0], [0,1], [-1,0],[0,-1]]
c_li = set()
v_li = set()
r,c = map(int,sys.stdin.readline().split())
my_list = [[0] for _ in range(r+1)]
for i in range(1,r+1) :
    temp = list(map(int,sys.stdin.readline().split()))
    for k in temp :
        my_list[i].append(k)

my_time = 0

while 1:
    v = [[0 for _ in range(c + 1)] for _ in range(r + 1)]
    if sol() == True :
        print(my_time)
        break
    my_time +=1