[구현] 백준 2638번: 치즈 / 골드 4

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

2638번: 치즈

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

www.acmicpc.net

x_lim, y_lim = map(int, input().split())

# count the initial num of cheese
cheese = 0
graph = []
for i in range(x_lim):
    row = list(map(int, input().split()))
    graph.append(row)
    for j in range(y_lim):
        if row[j] == 1:
            cheese += 1

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ext = 2

# count the num of area that contacts with external air
def check(x, y):
    count = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if graph[nx][ny] == ext:
            count += 1
    return count

def bfs(q):
    while q:
        x, y = q.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < x_lim and 0 <= ny < y_lim and not visit[nx][ny]:
                visit[nx][ny] = True
                if graph[nx][ny] == 0:
                    graph[nx][ny] = ext
                    q.append([nx, ny])

# using bfs, check the external air and set the value to 2
# to divide external / internal air
visit = [[False]*y_lim for _ in range(x_lim)]
visit[0][0] = True
graph[0][0] = ext
bfs([[0, 0]])

answer = 0
while cheese > 0:
    answer += 1

    q = []
    for x in range(x_lim):
        for y in range(y_lim):
            if graph[x][y] == 1:
                if check(x, y) >= 2:
                    visit[x][y] = True
                    q.append([x, y])
                    cheese -= 1

    for x, y in q:
        graph[x][y] = ext

    bfs(q)

print(answer)