[BOJ 백준] 2638번 : 치즈 - 파이썬, Python

 

www.acmicpc.net/problem/2638

2638번: 치즈

 

 

 

문제의 구현 로직은 다음과 같다.

1. 모든 치즈가 다 녹았는지 확인한다. 남은 치즈가 있다면 전부 녹을 때 까지 아래의 과정을 반복한다.
2. 다른 치즈 내부 공간에 있지 않은 치즈들 중 외부 공기와 2개 변 이상 접촉한 치즈를 체크한다.
3. 체크된 치즈를 녹인다.

 

1, 3번은 크게 어렵지 않은데 2번이 조금 까다로운 편이었다.

 

 

단순히 상,하,좌,우 중 공기인 칸이 2개 이상인지만 확인하면 안된다.

왜냐하면 상하좌우의 2개 칸에 치즈가 없더라도, 치즈 내부에 있는 공간일 수 있기 때문이다.

 

 

아래 그림처럼 빨간색, 파란색 칸 모두 2개 변이 공기와 맞닿아 있지만, 파란색 칸은 다른 치즈 내부 공간에 있는 치즈이기 때문이다.

 

 

이를 해결하기 위해 외부 공기를 따로 처리하는 로직이 필요하다

• 이차원 리스트를 돌면서 4방탐색을 진행한다.
• 다음 진행 방향이 치즈면 큐에 넣는다
  • 리스트의 범위를 초과하지 않아야 한다.
  • 이미 큐에 넣은 좌표를 다시 넣지 않아야 한다.
• 큐에 들어간 좌표는 리스트에서 -1로 업데이트 한다.

 

이렇게 하면 내부 치즈와 맞닿은 공기들은 0으로 되어있고 외부 치즈와 맞닿은 공기만 -1로 된다.

 

왜냐면 큐에 치즈의 좌표를 넣지 않았기 때문에 치즈 내부의 공간으로 들어갈 수 없기 때문이다.

 

 

 

 

 

 

소스코드

 

import sys
from collections import deque
dy = [-1, 1, 0, 0]
dx = [0,0,-1,1]
n, m = map(int, sys.stdin.readline().split())
visited = [[False]*m for _ in range(n)]
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
answer = 0

# 바깥 공기를 -1로 초기화
def outSide():
    dq = deque()
    out_visited = [[False]*m for _ in range(n)]
    dq.append((0,0))
    out_visited[0][0] = True
    board[0][0] = -1
    while dq:
        y, x= dq.popleft()        
        for i in range(4):
            ny = dy[i] + y
            nx = dx[i] + x
            if 0 > ny or ny >=n or 0 > nx or nx>= m: continue
            if board[ny][nx] == 1 or out_visited[ny][nx]: continue 
            dq.append((ny,nx))
            board[ny][nx] = -1
            out_visited[ny][nx] = True
    return

# 치즈가 다 녹았는지 확인
def isMelt():
    for i in range(n):
        for j in range(m):
            if board[i][j] == 1:
                return False
    return True

while not isMelt(): # 치즈가 다 녹을 때 까지 반복    
    outSide()   # 바깥 공기를 -1로 초기화
    check = []  # 바깥 공기와 맞닿은 칸을 저장
    # 외부 공기와 접촉한 치즈 녹음
    for i in range(n):
        for j in range(m):
            if board[i][j] == 1:
                cnt = 0 # 바깥 공기와 맞닿은 칸의 개수
                for k in range(4):
                    ny = dy[k] + i
                    nx = dx[k] + j
                    if 0 > ny or ny >=n or 0 > nx or nx>= m: continue
                    if board[ny][nx] == -1: 
                        cnt += 1
                if cnt >= 2: # 2칸 이상 맞닿아야지 녹을 수 있음
                    check.append([i, j])    
    for y, x in check: # 바깥 공기와 맞닿은 칸은 녹음
        #print(y, x)
        board[y][x] = 0    
    answer += 1 


print(answer)