🥚문제

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

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션
• 깊이 우선 탐색

---

🥚입력/출력

---

🍳코드

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

# (0, 0)에서 bfs, 1을 만나면 바깥공기와 접촉하는 치즈조각


def melt(arr):
    q = deque([(0, 0)])
    # visited 표시
    # 방문X : -1
    # 공기  : 0
    # 치즈  : 공기와의접촉횟수(>= 1)
    visited = [[-1]*M for _ in range(N)]
    dr = [0, 0, -1, 1]
    dc = [-1, 1, 0, 0]

    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                # 공기
                if arr[nr][nc] == 0:
                    if visited[nr][nc] == -1:
                        visited[nr][nc] = 0
                        q.append((nr, nc))
                # 치즈
                elif arr[nr][nc] == 1:
                    if visited[nr][nc] == -1:
                        visited[nr][nc] = 1
                    else:
                        visited[nr][nc] += 1

    # visited[r][c] >= 2인 치즈들은 제거한다
    new_arr = copy.deepcopy(arr)
    for r in range(N):
        for c in range(M):
            if visited[r][c] >= 2:
                new_arr[r][c] = 0
    return new_arr


def all_melt(arr):
    for r in range(N):
        for c in range(M):
            if arr[r][c] == 1:
                return False
    return True


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

ans = 0
while not all_melt(arr):
    arr = melt(arr)
    ans += 1

print(ans)

---

🧂아이디어

구현, 탐색

• [백준 2636]치즈 문제와 유사한 문제이다.

• 차이점이 있다면 [백준 2636]치즈 문제는 공기와 접촉한 치즈가 녹아 없어지는 반면, 본 문제에서는 공기와 2변 이상이 접촉한 치즈가 녹아 없어진다는 것이다. 따라서 공기와의 접촉 횟수를 구해줘야 한다.

• 맨 가장자리에는 치즈가 놓이지 않으므로, ⭐(0, 0)에서 bfs를 하며 만나는 "1"⭐, 은 바깥 공기와 접촉하는 치즈 조각이다.

• 방문 여부를 표시하는 visited리스트를 유지하며 (nr, nc)위치에서 바깥 공기와 접촉하는 치즈조각을 만났을 때,
  (1) 첫 방문이라면 visited[nr][nc] = 1로,
  (2) 이미 방문한 적이 있다면 visited[nr][nc] += 1로 업데이트 해주며 공기와의 접촉 횟수를 구한다.

• bfs를 마친 뒤 visited리스트를 살펴보며 값이 2 이상인 좌표 (r, c)에 있는 치즈를 녹이고 (new_arr[r][c] = 0),
  치즈를 녹인 새로운 리스트를 반환한다(return new_arr).