[백준_2636] 치즈 with Python

백준(BOJ) 시뮬레이션: 치즈(골드 5)

문제 출처: https://www.acmicpc.net/problem/2636

2636번: 치즈

 

1. 알고리즘

• 녹은 치즈가 없을 때까지 while 문 반복
• 치즈 덩어리의 edge를 찾는 find_cheese_edge 함수를 작성. BFS 알고리즘 사용.
  • graph의 빈 공간을 탐색
  • 치즈 덩어리를 만나면 값을 2로 변경하고 치즈 edge 리스트(find_edge_list)에 추가
  • 치즈 덩어리가 존재했을 경우, 치즈를 녹이고 녹은 치즈의 갯수를 세는 melting_cheese 함수 호출
    • 치즈 edge 리스트에 따라 graph의 치즈 edge를 0으로 변경
    • 녹은 치즈의 갯수를 셈
  • 치즈 존재 여부, 함수 처리 후의 graph, 녹은 치즈 갯수 반환
  • 치즈 덩어리가 존재하지 않았을 경우, 치즈 존재 여부, graph, 녹은 치즈 갯수(0)을 반환
• 치즈 존재하지 않을 경우
  • 치즈가 다 녹은 시간과 이전에 녹은 치즈의 갯수를 출력
  • break로 while 반복 종료
• 치즈가 존재할 경우
  • 치즈의 녹은 시간 + 1
  • 녹은 치즈의 갯수(melted_cheese) 저장

 

2. 유의 사항

 

 

3. 어려웠던 점, 해결방법

• 치즈 덩어리의 edge만 탐색하려면 어떻게 처리해야할 지 고민했음.
  • 1을 탐색해야한다는 생각 때문에, 이전에 풀었던 다리 만들기 2 문제와 비슷한 방법을 생각했음.
    • 0에서 1을 만나는 경우에 처리를 해주고, 1에서 0을 만나는 경우를 처리해주는 방법을 생각했지만, 이 경우에는 가운데 뚫린 부분도 edge로 처리가 되기 때문에 안됐음
  • 0을 탐색한다는 생각으로 접근했어야 했음. 1의 치즈덩어리가 아닌, 0의 빈 외곽 덩어리를 찾는다는 접근이 필요

 

4. 소스코드

상세 코드 설명은 주석

import sys
from collections import deque
 
#치즈 외곽을 찾는 함수
def find_cheese_edge(start, graph):
    route = deque([start])
    visited = [[0]*M for _ in range(N)]
    visited[start[0]][start[1]] = 0
 
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    #외곽 좌표 리스트, 치즈 존재 여부
    find_edge_list, is_cheese = [], False
    while route:
        x, y = route.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            
            #탐색 좌표가 사각형 판 밖일 경우
            if not 0<=nx<N or not 0<=ny<M:
                continue
            
            #graph의 탐색 좌표가 0(빈 공간)이고, 방문한 적 없을 때
            if graph[nx][ny] == 0 and visited[nx][ny] == 0:
                route.append((nx, ny))
                visited[nx][ny] = 1
            #graph의 탐색 좌표가 1(치즈)이고, 방문한 적 없을 때
            elif graph[nx][ny] == 1 and visited[nx][ny] == 0:
                #graph 값 변경
                graph[nx][ny] = 2
                visited[nx][ny] = 1
                
                #치즈 존재
                is_cheese = True
                #외곽 리스트에 좌표 추가
                find_edge_list.append((nx, ny))
    
    #치즈가 존재하면
    if is_cheese:
        #치즈를 녹인 후, 녹은 그래프, 녹은 치즈 갯수를 반환받음
        after_melting_graph, melt_cheese_num = melting_cheese(graph, find_edge_list)
        #치즈 존재 여부, 녹인 후 그래프, 녹은 치즈 갯수 반환
        return is_cheese, after_melting_graph, melt_cheese_num
    else:
        #치즈 존재 여부, 녹인 후 그래프, 녹은 치즈 갯수(0) 반환
        return is_cheese, graph, 0
 
 
#치즈를 녹이는 함수
def melting_cheese(graph, edge_list):
    #녹은 치즈 갯수 변수
    count_melt_cheese = 0
    #치즈 외곽 좌표 갯수만큼 반복
    for x, y in edge_list:
        #치즈를 녹임
        graph[x][y] = 0
        #녹은 치즈 갯수 + 1
        count_melt_cheese += 1
 
    return graph, count_melt_cheese
 
 
input = sys.stdin.readline
if __name__ == '__main__':
    N, M = map(int, input().split())    #NxM크기
    cheese_board = [list(map(int, input().split())) for _ in range(N)]
    
    #녹이는 시간, 녹였던 치즈 갯수
    count_melt_time, melted_cheese = 0, 0
    while True:
        #치즈 존재여부, 녹은 후 치즈보드, 녹은 치즈 갯수
        is_melt, melt_cheese, cheese_num = find_cheese_edge((0, 0), cheese_board)
        #치즈가 존재하지 않은 경우, 녹인 시간, 이전 단계에서 녹였던 치즈 갯수 출력 후 반복문 종료
        if not is_melt:
            print(count_melt_time)
            print(melted_cheese)
            break
        
        #녹인 시간+1
        count_melt_time += 1
        #녹은 치즈 갯수 저장
        melted_cheese = cheese_num
 

 

5. 고민

• BFS 탐색 중, graph의 값을 2로 바꿔주는 연산이 필요했나? 필요 없었을 것...
• 마지막 단계에서는 치즈가 없으니까 N*M만큼 탐색을 진행하게 되는데, 연산을 줄이려면 어떻게 할 수 있을까
  • 녹은 치즈 갯수, 전체 판 크기, 0의 갯수와 비교해서 녹인 후 치즈가 존재하는 지 반환?