본문 바로가기
알고리즘/백준

[백준]230214 문제풀이

by stubborngastropod 2023. 2. 14.
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

댓글