[BOJ][Python] 백준 2636번: 치즈

1일 1PS 37일차! .. 다시 이어서 시작

📚 문제

---

골드 4

• 치즈가 주어지는 크기가 100 뿐이므로 그냥 단순 탐색을 하면 된다고 생각했다.
• 하지만 비어있지만 치즈로 둘러쌓여있는 곳은 공기가 안들어간다는 조건으로 인해 bfs 를 사용해야했다.
• dfs 를 사용해서 겉에 있는 치즈들을 순차적으로 없애나가면 된다.

💡 풀이 과정

---

1. DFS 로 가장 겉에 있는 치즈의 위치를 파악한다.
2. 겉에 있는 치즈의 수를 저장해놓고 겉의 치즈를 모두 없앤다.
3. 시간 경과 카운팅을 추가하며 이를 반복한다.
4. 마지막에 없앨 치즈가 존재하지 않는다면 종료하고 카운팅과 마지막으로 저장한 치즈의 수를 출력한다.

💻 코드

---

n, m = map(int, input().split())

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

matrix = []
for _ in range(n):
    matrix.append(list(map(int, input().split())))

target = set()
last_target = 0
flag = True
cnt = 0

while flag:
    visited = [[False for _ in range(m)] for _ in range(n)]

    stack = []
    stack.append([0, 0])
    while stack:
        i, j = stack.pop()

        for k in range(4):
            nx, ny = i + dx[k], j + dy[k]

            if nx < 0 or ny < 0 or nx >= n or ny >= m or visited[nx][ny] == True:
                continue

            visited[nx][ny] = True
            if matrix[nx][ny] == 0:
                stack.append([nx, ny])
            else:
                target.add((nx, ny))

    if not target:
        flag = False
        break

    for x, y in target:
        matrix[x][y] = 0

    cnt += 1
    last_target = len(target)
    target.clear()

print(cnt)
print(last_target)