Problem Solving/백준
[BOJ 백준] 2638번 : 치즈 - 파이썬, Python
돌돌김
2021. 1. 8. 02:27
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표
www.acmicpc.net
문제의 구현 로직은 다음과 같다.
- 모든 치즈가 다 녹았는지 확인한다. 남은 치즈가 있다면 전부 녹을 때 까지 아래의 과정을 반복한다.
- 다른 치즈 내부 공간에 있지 않은 치즈들 중 외부 공기와 2개 변 이상 접촉한 치즈를 체크한다.
- 체크된 치즈를 녹인다.
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)