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

🥚문제

🥚입력/출력

🍳코드

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


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


def mark_air(arr):
    # 치즈의 구멍과, 바깥 공기를 구분하기 위해
    # arr에서 치즈 바깥에 있는 공기들을 -1로 표시한다
    # (0, 0)은 항상 공기이므로, 시작점으로 잡는다
    visited = [[False]*m for _ in range(n)]
    dr = [0, 0, -1, 1]
    dc = [-1, 1, 0, 0]

    q = deque([(0, 0)])
    visited[0][0] = True
    arr[0][0] = -1

    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 and not visited[nr][nc]:
                    visited[nr][nc]
                    q.append((nr, nc))
                    arr[nr][nc] = -1


def melt(arr):
    mark_air(arr)
    new_arr = [row[:] for row in arr]

    dr = [0, 0, -1, 1]
    dc = [-1, 1, 0, 0]

    for r in range(n):
        for c in range(m):
            if arr[r][c] == 1:
                for i in range(4):
                    nr = r + dr[i]
                    nc = c + dc[i]
                    # 상, 하, 좌, 우로 바깥 공기와 접촉 시
                    if arr[nr][nc] == -1:
                        new_arr[r][c] = 0
                        break

    # -1로 마크해놓은 바깥 공기 다시 0으로 돌림
    for r in range(n):
        for c in range(m):
            if new_arr[r][c] == -1:
                new_arr[r][c] = 0

    return new_arr


def count_chesses(arr):
    cnt = 0
    for r in range(n):
        for c in range(m):
            if arr[r][c] == 1:
                cnt += 1
    return cnt


def no_cheese(arr):
    for r in range(n):
        for c in range(m):
            if arr[r][c] == 1:
                return False
    return True


ans = 0
while True:
    new_arr = melt(arr)
    ans += 1

    if no_cheese(new_arr):
        print(ans)
        print(count_chesses(arr))
        break

    # update
    arr = [row[:] for row in new_arr]

🧂아이디어

구현, 탐색

• 바깥 공기와, 치즈의 구멍을 구분해야 했다.

• 주어지는 입력에서, 판의 가장자리는 항상 치즈가 없는 0이다.

• (0, 0) 위치에서 bfs를 하며 0인 위치들을 -1로 바꾸어준다면 바깥 공기는 -1로, 치즈의 구멍(치즈로 둘러싸인 0)은 그대로 0인 상태로 남아있을 것이다.

• 상, 하, 좌, 우로 바깥공기인 "-1" 과 접촉한다면 치즈를 녹이면 된다.

• 또한, 문제에서 치즈가 모두 녹아 없어지는 시간과 치즈가 모두 녹기 한 시간 전의 치즈조각 개수를 출력하기를 요구하므로

• arr을 치즈를 녹이기 전 상태, new_arr를 치즈를 녹인 후의 상태로 유지한다.

➕ 개선

(0, 0)에서 bfs를 하며 "1"을 만나면, 이는 바깥 공기와 접촉하는 치즈 조각이라는 의미이다.
바깥 공기를 -1로 마크해 줄 필요 없이, 처음부터 공기와 접촉하는 치즈 조각의 위치를 구한다면 훨씬 깔끔한 코드를 짤 수 있다.

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


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


def melt(arr):
    # 치즈가 녹은 후의 상태
    new_arr = [row[:] for row in arr]

    # 공기에 접촉하는 치즈 녹이기
    air_cheese = get_air_cheese(arr)

    while air_cheese:
        r, c = air_cheese.popleft()
        new_arr[r][c] = 0

    return new_arr


def get_air_cheese(arr):
    # 공기에 접촉하는 치즈의 위치 구하기
    air_cheese = deque([])

    visited = [[False]*m for _ in range(n)]
    # (0, 0)에서 탐색 시작
    q = deque([(0, 0)])
    visited[0][0] = True

    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 and not visited[nr][nc]:
                    q.append((nr, nc))
                    visited[nr][nc] = True

                # 공기와 접촉하는 치즈의 위치
                elif arr[nr][nc] == 1 and not visited[nr][nc]:
                    air_cheese.append((nr, nc))
                    visited[nr][nc] = True
    return air_cheese


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


def count_cheese(arr):
    ans = 0
    for r in range(n):
        for c in range(m):
            if arr[r][c] == 1:
                ans += 1
    return ans


ans = 0  # 걸리는 시간
while True:
    new_arr = melt(arr)
    ans += 1

    # 다 녹았는가?
    if all_melt(new_arr):
        print(ans)
        # 녹기 한시간 전 치즈조각 개수
        print(count_cheese(arr))
        break

    # update
    arr = [row[:] for row in new_arr]