백준 - 2638번(BFS,구현)

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

2638번: 치즈

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())

arr = []
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

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

def bfs():
    q = deque([])
    q.append([0,0])
    visited[0][0] = True
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx <n and ny>=0 and ny <m and visited[nx][ny] == False:
                if arr[nx][ny] >= 1:
                    arr[nx][ny] = arr[nx][ny] + 1
                else:
                    visited[nx][ny] = True
                    q.append([nx,ny])
ans = 0

while 1:
    visited = [[False for _ in range(m)] for _ in range(n)]
    bfs()
    ck = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] >= 3:
                arr[i][j] = 0
                ck = 1
            elif arr[i][j] == 2:
                arr[i][j] = 1

    if ck == 1:
        ans = ans + 1
    else:
        break

print(ans)

문제를 이해하고 쉽게 생각해보면 2칸 이상 접촉한 것들 중 가장 바깥쪽에 있는 애들부터 사라진다.

따라서 좌표의 값이 0인 좌표들만 bfs로 탐색해주고 방문 처리를 해준다. 만약 1 이상을 만나게 된다면 그것은 맞닿아 있는 빈칸의 개수를 세줘야 한다. 따라서 좌표에 도달할 때마다 1을 추가해준다.

while 1의 내부를 보면 배열을 탐색해서 좌표의 값이 3이 이상인 좌표들을 0으로 바꿔준다. 즉 좌표 값이 3 이상이라는 소리는 적어도 2개 이상의 접촉면을 가진다는 의미이다. 만약에 좌표의 갑이 2인 경우 한 면만 맞닿아 있는 것으로 다시 1로 바꿔준다.

while 문이 실행될 때마다 visit 배열을 초기화해준다. while문의 한 번의 실행이 문제 기준으로 1시간인 것이다.

따라서 조건에 맞게 ans의 값을 1씩 증가해준다. 만약 ck가 0이라면 더 이상 녹을 치즈가 없다는 의미이다. 반복문을 탈출한다.