[2636번] 치즈

문제 출처 :

 

www.acmicpc.net/problem/2636

2636번: 치즈

 

 

 

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

 

 

- 가장 겉면에 있는 1을 모두 찾고

- 그다음 찾은 인덱스를 모두 지워주는 방식으로 진행하면 쉽게 해결 가능하다.

 

 

 

아래 코드에서 재미있는건 

2차원 배열을 1차원화 시켜서 list comprehension으로 리스트에서 1만 추출한 후 해당 len을 구하면 1의 개수를 구할 수 있게 된다.

flat = sum(arr, [])
lastCount = len([i for i in flat if i])

 

소스 코드 : 

 

 

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

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]


def getStartQueue():
    q = []
    startq = []
    visit = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                q.append([i, j])
                break
        if len(q) != 0:
            break

    while True:
        if len(q) == 0:
            break

        y, x = q.pop(0)

        if visit[y][x]:
            continue

        visit[y][x] = 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n:
                if arr[ny][nx] and not visit[ny][nx]:
                    visit[ny][nx] = 1
                    startq.append([ny, nx])
                if arr[ny][nx] == 0:
                    q.append([ny, nx])

    return startq


def eatCheese(startq):
    while True:
        if len(startq) == 0:
            break

        y, x = startq.pop(0)
        arr[y][x] = 0


lastCount = 0
lastDay = 0
while True:
    startq = getStartQueue()

    if len(startq) == 0:
        break

    lastDay += 1

    flat = sum(arr, [])
    lastCount = len([i for i in flat if i])

    eatCheese(startq)

print(lastDay)
print(lastCount)