[Python] BOJ 2636 - 치즈

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

2636번: 치즈

# BFS+시뮬레이션 문제이다.

# 최근에 푼 문제중에 가장 오래걸렸다..

 

* bfs함수: (15 ~ 20라인)은 현재 좌표기준으로 상하좌우를 탐색하면서 m[nx][ny]가 2인지 아닌지 판단한다.

              m[nx][ny]가 2이면 공기와 닿아있는 좌표이므로 move에 넣어주고 cnt를 1증가시킨다.

              상하좌우 중 한 곳이라도 공기와 닿아있으면 녹으므로 바로 break를 해준다.

 

             맵 탐색을 마친뒤 [cnt, move]를 return 해준다.

              (cnt: 이번 턴에 녹을 치즈의 개수, move: 녹을 치즈의 좌표들)

 

* edge함수: 맵 전체를 돌면서 0이거나 2인 칸을 2로 바꿔준다. (공기가 존재하는 칸)

 

* cheese에 처음 치즈개수를 저장해주고 메인함수를 실행한다 (55라인 ~ )

   매일매일 edge함수를 통해 공기가 있는 칸을 갱신해주고 반복문을 돌며

   m[i][j]가 1이고 방문하지 않은 칸이면 bfs(i, j, visited, cnt, move)를 실행한다.

   (하루 동안 맵을 탐색할 때, 이어지지 않고 떨어진 곳이 있으면 bfs함수가 중간에 return으로 끊기고

   다시 bfs함수가 실행되기 때문에 그 과정에서 visited와 cnt, move를 유지하기 위해 매개변수로 넘겨준다.)

   

   bfs함수를 실행한 뒤 리턴 값은 res = [cnt, move]이므로 cnt에 res[0]값을 더해주고

   move = res[1]로 move도 갱신해준다.

   맵 전체를 확인 한 뒤에 res[0]에는 총 녹을 치즈의 개수, res[1]에는 녹을 치즈의 좌표들이 저장되어있다.

   

   cheese에서 res[0]을 빼주고 cheese가 0이라면 모든 치즈가 다 녹은 것이므로

   day+1과 0이 되기 이전의 치즈개수인 res[0]을 출력해주고

   0이 아니라면 res[1]에 있는 좌표들을 2로 바꾼 뒤 day를 1 증가시킨다.

 

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
sero, garo = map(int,input().split())
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
m = [list(map(int,input().split())) for _ in range(sero)]
q = deque()

def bfs(i, j, visited, cnt, move):
    q.append((i, j))
    visited[i][j] = True
    while q:
        x, y = q.popleft()
        # 공기에 닿아있는 치즈 좌표 move에 넣고 cnt증가
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if m[nx][ny] == 2:
                move[(x, y)] += 1
                cnt += 1
                break
        
        # 상하좌우로 맵 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < sero and 0 <= ny < garo and not visited[nx][ny]:
                if m[nx][ny] == 1:
                    visited[nx][ny] = True
                    q.append((nx, ny))

    return [cnt, move]

# 공기가 있는 부분 2로 바꿔줌
def edge():
    visited = [[False] * garo for _ in range(sero)]
    q.append((0, 0))
    visited[0][0] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < sero and 0 <= ny < garo and not visited[nx][ny]:
                if m[nx][ny] == 0 or m[nx][ny] == 2:
                    m[nx][ny] = 2
                    visited[nx][ny] = True
                    q.append((nx, ny))

# 처음 치즈개수 저장
cheese = 0
for i in range(sero):
    for j in range(garo):
        if m[i][j] == 1:
            cheese += 1

day = 0
while True:
    # 매일매일 공기가 들어오는 부분 갱신
    edge()
    move = defaultdict(int)
    cnt = 0
    visited = [[False] * garo for _ in range(sero)]
    for i in range(sero):
        for j in range(garo):
            if m[i][j] == 1 and not visited[i][j]:
                res = bfs(i, j, visited, cnt, move)
                cnt, move = res[0], res[1]
    
    cheese -= res[0]
    if cheese == 0:
        print(day+1)
        print(res[0])
        break
    else:
        for i, j in res[1]:
            m[i][j] = 2
        day += 1

(solved.ac 티어: 골드 5)

 

# 진짜 꾸역꾸역 어거지로 푼 느낌이다.. 다른 분들의 코드를 보고 개선을 해야할 듯