[python] 2636. 치즈

문제 출처

2636. 치즈

 

풀이

주어진 배열에서 가장 외각부터 안쪽으로 한 단계씩 들어가며 모두 없어질 때까지의 시간과 마지막에 남은 치즈의 갯수를 구하는 문제이다. 입력은 가로, 세로 최대 100이며 제한 시간은 1초 이므로 기본적인 BFS 탐색으로도 충분 하다.

 

1. 치즈가 없어질때 까지의 시간 time과 시간별로 없어지는 치즈의 수인 cnt를 0으로 초기화 한다.
2. 주어진 배열의 상하좌우에 0을 추가해 준다.
3. 치즈가 존재하지 않는 (0, 0) 인덱스를 q에 추가해 준다.
4. q에서 처음꺼를 pop해서 배열의 상하좌우를 탐색하며 아래 조건에 해당하는 인덱스만 q에 추가한다.
   • 배열의 범위(0 <= row < N+2, 0<= column < M+2)를 초과하는 값은 추가하지 않는다.
   • 치즈가 존재하지 않는 인덱스는 q에 추가해 주고, 해당 위치의 값을 -1로 바꿔준다.
   • 치즈가 존재하는 인덱스는 nxt에 추가해 주고, 마찬가지로 값을 -1로 바꿔준다.
   • 이 작업을 q가 빈 리스트가 될 때까지 반복한다.
5. 3번 작업이 끝나고 nxt의 값이 빈 리스트이면 배열에 치즈가 더이상 존재하지 않는것이므로 while문을 종료한다.
6. time을 1초 증가하고 nxt의 길이를 구해 다음에 없어질 치즈의 갯수를 저장한다.
7. 4번 작업에서 -1로 바꿔 방문한 곳을 표시한 인덱스를 모두 0으로 바꿔준 후 위 작업을 nxt가 빈 배열이 될 때까지 반복한다.

 

N, M = map(int, input().split())
arr = [[0]*(M+2)] + [[0] + list(map(int, input().split())) + [0] for _ in range(N)] + [[0]*(M+2)]

cnt, time = 0, 0
while 1:
    nxt = []
    q = [(0, 0)]
    while q:
        y, x = q.pop(0)
        for dx, dy in (0, -1), (1, 0), (0, 1), (-1, 0):
            ny, nx = y+dy, x+dx
            if nx < 0 or nx >= M+2 or ny < 0 or ny >= N+2:
                continue
            if arr[ny][nx] == 0:
                arr[ny][nx] = -1
                q.append((ny, nx))
            if arr[ny][nx] == 1 :
                arr[ny][nx] = -1
                nxt.append((ny, nx))

    if not nxt:
        break

    time += 1
    cnt = len(nxt)
    for y in range(N+2):
        for x in range(M+2):
            if arr[y][x] == -1:
                arr[y][x] = 0

print(f'{time}\n{cnt}')