BOJ:2636チーズ


bfsを利用した.最初はエッジがdefault空気であることを知らず、エッジに空気が入っている部分を見つけ、startリストに入れてbfsを回したが失敗した.(0,0)だけ入れて、すぐに成功したのに、どうして、
import sys
from collections import deque
# 치즈가 모두 녹아 없어지는 데 걸리는 시간과, 모두 녹기 한 시간 전에 치즈 조각이 놓여있는 칸의 개수를 구하자
sys.setrecursionlimit(11111)

def isCheeze(h, w):
    if cheeze[h][w] == 1:
        return True
    return False


def bfs(group, day):
    cheeze = set()
    air = set()
    for h, w in group:
        global visit
        visit[h][w] = day
        for (i, j) in [(1,0),(-1,0),(0,1),(0,-1)]:
            new_h, new_w = (h + i, w + j)
            if 0 <= new_h < height and 0 <= new_w < width:
                if isCheeze(new_h, new_w) and (visit[new_h][new_w] == -1 or visit[new_h][new_w] > day + 1):
                    cheeze.add((new_h, new_w))
                elif not isCheeze(new_h, new_w) and (visit[new_h][new_w] == -1 or visit[new_h][new_w] > day):
                    air.add((new_h, new_w))
    if air:
        bfs(air, day)
    if cheeze:
        bfs(cheeze, day + 1)



input = sys.stdin.readline

height, width = list(map(int, list(input().strip().split())))

cheeze = [list(map(int, list(input().strip().split()))) for _ in range(height)]
# (x,y)좌표 cheeze => cheeze[y - 1][x - 1]
visit = [[-1] * width for _ in range(height)]

# 처음 가장자리 중 공기가 있는 부분 찾기
start = [(0,0)]
# for h in [0, height - 1]:
#     for w in range(0, width):
#         if not isCheeze(h, w):
#             start.append((h, w))
# for w in [0, width - 1]:
#     for h in range(0, height):
#         if not isCheeze(h, w):
#             start.append((h, w))
day = 0
bfs(start, day)



max = 0
max_count = 0
for h in range(height):
    for w in range(width):
        if visit[h][w] > max and isCheeze(h, w):
            max = visit[h][w]
            max_count = 1
        elif visit[h][w] == max and isCheeze(h, w):
            max_count += 1

print(max)
print(max_count)