[파이썬]백준 2636 치즈

링크

백준 2636 치즈

bfs를 살짝 응용해서 풀어야 하는 문제였다.
공기인 부분을 탐색하며 치즈 겉면의 좌표를 리턴하는 bfs를 만들었다.
단순히 겉면의 좌표를 전부 다 사용하면 중복이 생겨서 리턴 후 set로 중복을 제거해줬다.

그 후 받아온 치즈 겉면의 좌표를 0으로 전부 처리해준다.
그리고 치즈 겉면의 좌표를 시작점으로 하는 bfs를 실행해 새로운 치즈 겉면의 좌표를 받아오고 이를 반복한다.

만약 더이상 탐색할 치즈가 없으면 반복을 종료한다.

모두 녹기 전에 남아있는 치즈조각의 경우 치즈 겉면에 대한 bfs를 시작하기에 앞서 치즈겉면 좌표가 있는 리스트의 길이를 체크해서 출력했다.

오늘 하루종일 swea에서 한문제로 씨름하면서 고통받다가 저녁 공부땐 틀리는 것 없이 한번에 풀어서 기분이 너무너무좋았다..

정답 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(r, c):
    q = deque()
    q.append((r, c))
    tmp = []
    while q:
        r, c = q.popleft()
        arr[r][c] = -1
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < height and 0 <= nc < width:
                if arr[nr][nc] == 0:
                    arr[nr][nc] = -1
                    q.append((nr, nc))
                if arr[nr][nc] == 1 and arr[r][c] == -1:
                    tmp.append((nr, nc))
    return tmp


height, width = map(int, input().split())
arr = []
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
for _ in range(height):
    arr.append(list(map(int, input().split())))

cnt = 1
cheese = deque(set(bfs(0, 0)))

while True:
    tmp = []
    last = len(cheese)
    while cheese:
        for side in cheese:
            r, c = side[0], side[1]
            arr[r][c] = 0
        r, c = cheese.popleft()
        tmp += bfs(r, c)
    if tmp == []:
        break
    else:
        cheese = deque(set(tmp))
        cnt += 1

print(cnt, last, sep='\n')

알게된 것👨‍💻

• 코드먼저 짜지말고 어떻게 풀어야 할지 생각을 먼저하니 문제가 술술술