[BFS] 2636. 치즈

2636. 치즈

2636번: 치즈

 

• 내 풀이 - 실패
  • 치즈 입장에서 공기를 접하는지 확인 하려고함
  • 치즈내부 안의 공기를 고려하지 않음

 

• 다른 사람 풀이
  • 공기는 외부공기, 내부공기 2가지고 치즈는 한가지 이기 때문에  공기 → 치즈로 확인해야함
    • 치즈→공기는 2가지 경우가 있지만 공기→치즈는 한가지 경우만 확인하면 되기때문
    • 치즈입장에서도 2가지를 확인해야하면 짜증날 것
  • 마지막 남아있던 개수 셀 때
    
    • 남아있는 치즈 수를 세고 answer에 넣어줌
    • 1시간만에 0이 되는 경우:  주어진 치즈 수가 답이기 때문에 answer에 처음 치즈 수도 넣어줘야함

 

• 📍추가로 생각해보기
  • 이 문제처럼 양 끝에는 치즈가 오지 않는 경우가 아니면
  • 아래 경우처럼 (0,0) 만 확인했을때 도중에 가로막혀서 다른면을 확인하지 못하게될 수 있음
    •  → 5x5를 7x7로 생각하고 양 끝을 0으로 두번 감싼 후에 풀기

0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0

 

from collections import deque

r, c = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(r)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def check():
    queue = deque()
    visited = [[0 for _ in range(c)] for _ in range(r)]

    visited[0][0] = 1
    queue.append((0, 0))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            if visited[nx][ny] == 1:
                continue

            visited[nx][ny] = 1
            if graph[nx][ny] == 1:
                # 치즈 녹이고 queue에 추가안함(바깥쪽 치즈만 고려하면되므로)
                graph[nx][ny] += 1
            else:
                queue.append((nx, ny))

    count()


def count():
    global cnt
    for i in range(r):
        for j in range(c):
            if graph[i][j] == 1:
                cnt += 1


time = 0
cnt = 0
count()  # 가장 처음 개수
answer = []
answer.append(cnt)


while True:
    cnt = 0
    time += 1
    check()

    if cnt == 0:
        print(time)
        print(answer[-1])
        break

    answer.append(cnt)