백준 2638 치즈 파이썬 풀이 반례

난이도 : 골드3

풀이일 : 05151

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

2638번: 치즈

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 런타임에러(최대 재귀횟수 초과)

import sys
from collections import deque

def air(x, y):    # 외부 공간 숫자 변경
    space = deque()
    space.append((x, y))
    visited = [[0] * M for _ in range(N)]
    visited[x][y] = 1
    while space:
        i, j = space.popleft()
        for k in range(4):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < N and 0 <= nj < M and not arr[ni][nj] and not visited[ni][nj]:
                visited[ni][nj] = 1
                arr[ni][nj] = 2
                space.append((ni, nj))
    melt(arr)
    return

def melt(arr):
    global hour
    cheese = deque()    # 녹을 치즈 구하기
    temp = [[0] * M for _ in range(N)]    # 공기 인접 방향 수
    for x in range(N):
        for y in range(M):
            if arr[x][y] == 1:
                cheese.append((x, y))
                for z in range(4):
                    nx, ny = x + di[z], y + dj[z]
                    if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 2:
                        temp[x][y] += 1
    if not cheese:
        return print(hour)
    # 치즈 녹이기
    else:
        hour += 1
        while cheese:
            a, b = cheese.popleft()
            if temp[a][b] >= 2:
                arr[a][b] = 2
        air(0, 0)


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

di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
hour = 0

arr[0][0] = 2
air(0, 0)

코드 구성

• 외부 공간 숫자 2로 변경
• 치즈 존재 여부 확인, 연결되지 않는 치즈 덩어리 세서 deque 추가
• 치즈가 있다면, 시간 늘리고 치즈 녹이기
• temp로 녹일 지 판단 할 수 있는 외부 연결 수 확인
• 내부 공간 외부와 연결 여부 확인 -> 연결 시 2로 변경
• 치즈가 없을 때까지 반복 치즈가 없으면 시간 출력 반환

틀린 이유

• air 함수 내 arr[ni][nj]가 없을 때 queue에 추가하도록 하여 2일때 탐색 중단
• 맨 처음을 제외하면 숫자가 2일 때에도 탐색해야 함

---

최종 정답

# 외부 공간 숫자 2로 변경
# 치즈 존재 여부 확인, 연결되지 않는 치즈 덩어리 세서 deque 추가
# 치즈 녹이기 -> 시간 증가
# 내부 공간 외부와 연결 여부 확인 -> 연결 시 2로 변경

import sys
from collections import deque

def air(x, y):    # 외부 공간 숫자 변경
    space = deque()
    space.append((x, y))
    visited = [[0] * M for _ in range(N)]
    visited[x][y] = 1
    while space:    # 다시 visited 추가하고 재방문 방지
        i, j = space.popleft()
        for k in range(4):    # 상하좌우 방향 연결된 공간 확인
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj]:
                if not arr[ni][nj] or arr[ni][nj] == 2:
                    arr[ni][nj] = 2
                    space.append((ni, nj))
                    visited[ni][nj] = 1
    melt(arr)
    return

def melt(arr):
    global hour
    cheese = deque()    # 녹을 치즈 구하기
    temp = [[0] * M for _ in range(N)]    # 공기 인접 방향 수
    for x in range(N):
        for y in range(M):
            if arr[x][y] == 1:
                cheese.append((x, y))
                for z in range(4):
                    nx, ny = x + di[z], y + dj[z]
                    if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 2:
                        temp[x][y] += 1

    if not cheese:    # cheese 다 녹으면 시간 출력 반환
        return print(hour)
    else:    # 치즈 녹이기
        hour += 1
        while cheese:
            a, b = cheese.popleft()
            if temp[a][b] >= 2:    # 두 면 이상 외부 노출 시
                arr[a][b] = 2
        air(0, 0)    # 내부 공간 외부 연결 확인

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

di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
hour = 0

arr[0][0] = 2
air(0, 0)

코드 변화

• air 함수 속 외부 공간 상하좌우 연결 확인 시 arr[ni][nj] 2 or 0 일때 queue 추가

---

반례

입력	6 7 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
출력	3

---

느낀점

전에 풀었던 빙산 문제랑 유사하게 풀었다.

https://chadireoroonu.tistory.com/6

백준 2573 빙산 파이썬 풀이, 시간초과, 반례

역시 알고리즘이 제일 재미있어서 맨날 알고리즘만 풀고 싶다.

장고 싫고 뷰 싫어