[백준] 2636번 치즈 - python 파이썬

문제

 

 

이 문제를 처음 풀려고 했을 때는 너무 어렵게 느껴졌다. BFS로 풀어야되는 건 금방 알겠는데 어떻게 테두리 영역만 따로 구하고 테두리 영역중에서 구멍이랑 맞닿은 테두리 부분은 제외 해줘야할 지 감이 잘 안잡혔다.

 

 

하지만 이 문제는 생각을 조금만 다르게 해주면 금방 풀린다. 처음에는 치즈의 영역에 너무 집착 했는데 반대로 공기의 영역을 먼저 구해주면된다.

 

 

공기의 영역을 어떻게 구해주냐하면 가장자리는 항상 공기 부분이 되기 때문에 0,0 지점부터 BFS를 시작하여 인접한 부분중에 0인 부분만 방문해주면 된다. 그렇게 되면 구멍 부분을 제외한 공기부분이 전부 방문 처리 된다.

 

 

 

위 내용에 대한 그림 예시이다. 빨간색으로 칠한 부분이 전부 방문 처리 되게 된다.

 

이렇게 방문처리 해준 후 치즈가 있는 좌표가 방문 처리된 좌표와 맞닿아있다면 공기로 바꾸어 주면 된다.

 

정답 코드

from collections import deque
r,c = map(int,input().split())
graph = []
for _ in range(r):
    row = list(map(int,input().split()))
    graph.append(row)
dx = [0,0,1,-1]
dy = [1,-1,0,0]


#구멍이 아닌 공기만 방문
def bfs():
    #0,0은 판의 가장자리이므로 항상 0임
    q=deque([(0,0)])
    visited[0][0] = 1

    while(q):
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx<r and 0<=ny<c and visited[nx][ny] == 0 and graph[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx,ny))
pre = 0
cnt = 0
t = 0
for g in graph:
    cnt += g.count(1)

while True:
    #치즈가 사라지면 종료
    cnt = 0
    for g in graph:
        cnt += g.count(1)
    if cnt == 0:
        break
    visited = [[0]*c for _  in range(r)]
    #구멍을 제외한 공기만 방문하는 함수
    bfs()
    for i in range(r):
        for j in range(c):
            if graph[i][j] == 1:
                #공기와 맞닿은 테두리 부분인지 체크
                check = False
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0<= nx<r and 0<=ny<c and visited[nx][ny] == 1:
                        check = True
                        break
                #테두리면 삭제 진행
                if check:
                    graph[i][j] = 0
    pre = cnt
    t += 1


print(t)
print(pre)