728x90
2638. 치즈
from collections import deque
N, M = map(int, input().split())
lst = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
time = 0
for i in range(N):
a = list(map(int, input().split()))
lst.append(a)
while True:
cheeze = deque([])
# 공기부분 -1로 변환
lst[0][0] = -1
queue = deque([(0, 0)])
visited = [[False] * M for _ in range(N)]
while queue:
a = queue.pop()
visited[a[0]][a[1]] = True
temp = []
for k in range(4):
if a[0] + dx[k] not in range(N) or a[1] + dy[k] not in range(M):
continue
elif lst[a[0] + dx[k]][a[1] + dy[k]] == -1 and not visited[a[0] + dx[k]][a[1] + dy[k]]:
visited[a[0] + dx[k]][a[1] + dy[k]] = True
queue.appendleft((a[0] + dx[k], a[1] + dy[k]))
elif lst[a[0] + dx[k]][a[1] + dy[k]] == 0 and not visited[a[0] + dx[k]][a[1] + dy[k]]:
temp.append((a[0] + dx[k], a[1] + dy[k]))
visited[a[0] + dx[k]][a[1] + dy[k]] = True
queue.appendleft((a[0] + dx[k], a[1] + dy[k]))
elif lst[a[0] + dx[k]][a[1] + dy[k]] == 1 and not visited[a[0] + dx[k]][a[1] + dy[k]]:
visited[a[0] + dx[k]][a[1] + dy[k]] = True
cheeze.appendleft((a[0] + dx[k], a[1] + dy[k]))
for i in temp:
lst[i[0]][i[1]] = -1
# 빈 리스트인지 확인
cnt = 0
for i in lst:
if i == [-1] * M:
cnt += 1
if cnt == N:
break
# 녹는 치즈 찾기
time += 1
visited = [[False] * M for _ in range(N)]
temp = []
while cheeze:
a = cheeze.pop()
visited[a[0]][a[1]] = True
air = 0
for k in range(4):
if lst[a[0] + dx[k]][a[1] + dy[k]] == -1:
air += 1
if air >= 2:
temp.append(a)
for i in temp:
lst[i[0]][i[1]] = -1
print(time)
BFS는 전부 이렇게 토나오는 코드로만 짤 수 있는건가? 싶을 정도로 악랄한 인덱싱... 처음으로 푼 골3 문제라 뿌듯하기도 하지만, 어느정도 실력이 잡히고 나면 얼른 클린코드를 위한 공부를 하고싶다는 생각이 드는 하루였다.
dp는 골드 문제 몇개 도전해보고 있었는데 진짜 손도 못대겠어서 다 내려놨다. SWEA에 있는 기초적인 문제도 못푸는 상태라 일단 브론즈~실버 하위권 문제부터 차근차근 풀면서 올라가봐야겠다.
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[백준]230217 문제풀이 (0) | 2023.02.18 |
---|---|
[백준]230215-16 문제풀이 (0) | 2023.02.16 |
[백준]230213 문제풀이 (0) | 2023.02.13 |
[백준]230210-12 문제풀이 (0) | 2023.02.12 |
[백준]230209 문제풀이 (0) | 2023.02.09 |
댓글