백준 2636번 파이썬 문제풀이(치즈) - (bfs + 구현 or 다익스트라)

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

2636번: 치즈

---

꽤 복잡한 BFS + 시뮬레이션 혹은 다익스트라로 해결할 수 있다. 

 

1. BFS + 시뮬레이션

from collections import deque

N, M = map(int, input().split())
cheese = [list(map(int, input().split())) for _ in range(N)]

visited = [[0] * M for _ in range(N)]
dr = [-1, 0, 1, 0]  # 상 우 하 좌
dc = [0, 1, 0, -1]  # 상 우 하 좌
pre_cnt = []


def bfs():
    total_time = 0  # 치즈가 녹는데 걸리는 시간
    queue = deque([[0, 0]])  # bfs를 돈다.
    while True:
        loc = set()  # 가장 바깥쪽 치즈들을 좌표들을 담을 셋
        while queue:
            r, c = queue.popleft()

            if cheese[r][c]:  # 만약 치즈가 1이라면
                continue  # 진행x

            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]

                if nr < 0 or nr >= N or nc < 0 or nc >= M or visited[nr][nc]:  # 범위를 벗어나거나 이미 방문했으면 진행x
                    continue

                if cheese[r][c] == 0 and cheese[nr][nc]:  # 만약 현재칸이 치즈가 없고 다음칸이 치즈가 있으면
                    loc.add((nr, nc))  # 해당 좌표를 저장

                if not cheese[nr][nc]:  # 만약 다음칸에 치즈가 없으면
                    visited[nr][nc] = 1  # 방문처리 후
                    queue.append([nr, nc])  # 해당 위치를 큐에 넣어준다.

        if not len(loc):  # 만약 더이상 녹을 치즈가 없으면
            return total_time  # 총 시간을 리턴

        for i in loc:  # 입력받은 치즈의 위치들을 돌아서
            queue.append([i[0], i[1]])  # 그 위치들을 큐에 넣어주고
            visited[i[0]][i[1]] = 1  # 해당 위치를 방문처리
            cheese[i[0]][i[1]] = 0  # 해당위치의 치즈를 0으로 녹여준다.

        total_time += 1  # 총 걸린 시간을 +1
        pre_cnt.append(len(loc))  # 이번시간에 녹은 치즈의 양을 추가


print(bfs())  # 총걸린시간 출력
print(pre_cnt[-1])  # 가장 마지막 치즈의 양을 출력

 

2. 다익스트라

import heapq

N, M = map(int, input().split())
cheese = [list(map(int, input().split())) for _ in range(N)]

dr = [-1, 0, 1, 0]  # 상 우 하 좌
dc = [0, 1, 0, -1]  # 상 우 하 좌
distance = [[1e10] * M for _ in range(N)]
time_ = 0


def bfs():
    global time_

    q = []
    heapq.heappush(q, (cheese[0][0], 0, 0))
    distance[0][0] = cheese[0][0]
    while q:
        cost, r, c = heapq.heappop(q)
        time_ = cost  # 걸린시간을 저장(마지막에 저장된 값이 제일 마지막에 녹은 치즈의 시간)

        if cost > distance[r][c]:
            continue

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= N or nc < 0 or nc >= M:
                continue
            # if cost + cheese[nr][nc] > 0 and not cheese[nr][nc]:
            #     heapq.heappush(q, (0, nr, nc))
            if cost + cheese[nr][nc] < distance[nr][nc]:
                distance[nr][nc] = cost + cheese[nr][nc]
                heapq.heappush(q, (distance[nr][nc], nr, nc))


bfs()
print(time_)

# 만약 1내부에 있는 0들도 같은 거리로 인식이 되기 때문에 해당 위치는 0으로 초기화 해주어야 한다.
for i in range(N):
    for j in range(M):
        if not cheese[i][j]:
            distance[i][j] = 0

count_ = 0  # 마지막에 남은 치즈 개수 체크
if time_ != 0:  # 만약 시간이 0아니라면(즉, 0은 체크하면 안됨)
    for i in distance:
        count_ += i.count(time_)
print(count_)