백준) 2636 치즈 문제풀이 및 set() 활용

문제

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

문제 해결

치즈가 공기중에 만나면 녹는다는 설명이 제일 중요하다.

공기가 정확히 무엇인지 설명해주지 않아서 유추하느라  시간이 많이 걸렸다..

여러 가설끝에 찾아낸 정답을 설명해보겠다.

 

아래 그림을 보면 c가 다음 시간에 녹는 치즈들을 표시해둔 것으로,

하얀색 부분이 공기라 맞닿은 면이 녹는건가? 라는 생각을 했다.

하지만 그렇게 가정하면 빨간색 화살표로 표시된 곳의 하얀색 부분도 공기인데

맞닿은 면들이 녹는 표시가 없으므로,

하얀색 면은 빈 공간이라 공기가 있을수도 있지만

치즈로 둘러쌓인 하얀색 면은 치즈 안쪽이라 공기가 없구나 라는 생각을 하게 되었다.  

 

그렇다면 항상 치즈 바깥에 있는 빈 공간 에서부터, 

하얀색 면들을 bfs로 전부 탐색한 후 맞닿은 치즈들을 녹이면 되겠다 라는 생각을 하였다.

(0,0) 은 항상 빈 공간이므로, 매 시간마다 (0,0)에서 bfs를 실행하여 치즈를 녹여가도록 하였다.

 

정답 코드 및 설명

• 맨 처음에 remain_chesee에 전체 치즈의 개수를 넣어주고,
• 시간이 지날때마다 사라지는 치즈들의 개수를 last_chesee로 세어준다.
• remain_chesee가 0 이 될때 , 지난 시간과 last_chesee의 값을 정답으로 출력해준다.

set을 활용한 부분

• 방문한 좌표를 담는 visited와 녹이는 치즈의 좌표를 담은 air가 있다.
• 이 둘은 리스트로 만들면 not in이나 in을 사용하면 O(n)만큼 시간이 걸리기때문에,
• 평균적으로 O(1)의 탐색시간이 걸리는 set()을 활용하여 효율을 높였다.

from collections import deque
#상 하 좌 우
dx=[-1,1,0,0]
dy=[0,0,-1,1]
# N=x N=y
N,M=map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
remain_cheese=0
last_chesee=0
ans_count=0
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            remain_cheese += 1

while remain_cheese>0:
    air=set()
    visited=set()
    q= deque()
    q.append([0,0])
    visited.add((0,0))
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if (nx,ny) not in visited and arr[nx][ny]==0:
                    q.append([nx,ny])
                    visited.add((nx,ny))
                elif (nx,ny) not in air and arr[nx][ny]==1:
                    air.add((nx,ny))
    for x,y in air:
        arr[x][y]=0
    last_chesee=len(air)
    remain_cheese -= last_chesee
    ans_count += 1
print(ans_count)
print(last_chesee)