11.22

오늘 푼 문제

• BFS
  • 2638 : 치즈 ✅
• DP
  • 11066 : 파일 합치기 ❌

문제 푼 흔적

기억할 만한 아이디어 및 느낀점

11066 파일 합치기

파일 합치기 문제는 질문 게시판에 어떤 분이 자료를 정리하신게 있어서, 자료를 보고 다시 풀어봐야겠다.

2638 치즈

치즈 문제도 그렇고, BFS 관련 문제를 풀 때 방문을 표시하기 위해 visit배열과, 처음에 주어지는 위치정보를 저장하기 위한 _map 배열을 둘 다 사용해야 하는 경우가 있다.

이때 문제가 요구하는 조건에 따라 visit을 따로 만들지 않고, visit의 내용을 _map에 표시하여 문제를 풀 수 있는 경우가 있다.

미리 생각하고 난 뒤에 문제를 풀면 괜찮지만, 그냥 부딪히면서 문제를 풀다보니 꼬리에 꼬리를 물고 문제가 발생하더라... 먼저 사용 용도를 정하고 문제를 풀자.

아무튼 문제는 다음과 같이 풀었다.

가장 중요한 부분은 치즈 내부의 공기와, 치즈 외부의 공기를 구분해야 하는 것인데, 처음에 가장자리에는 치즈가 놓이지 않는다는 부분을 못 보고 치즈가 안 놓인 부분이 외부 공기인지 내부 공기인지 알아내는 방법을 한참 고민했다.

가장자리에는 치즈가 놓이지 않는다는 조건이 붙는다면 다음과 같이 해결 가능하다.

• visit : 외부 공기가 방문한 곳
• _map
  • 0 : 내부 공기 (맨 처음에 외부 공기는 BFS를 통해 모두 2로 바뀜)
  • 1 : 치즈
  • 2 : 외부 공기

• (0,0)에서 BFS를 시작하여 도달하는 모든 공기에 대하여 _map에는 2로 표시하고, visit 배열에는 방문한 상태로 표시한다.

• _map 배열 전체를 돌면서 치즈이고, 외부 공기와 2면 이상 닿는 곳은 cheese_candidate에 담는다.

• cheese_candidate 에 담긴 치즈들을 다음과 같이 녹여준다

  • _map에서 2로 (외부 공기) 바꿔준다.
  • 현재 자리에서 4군데를 둘러봤을 때 내부 공기가 존재하는 지 확인한다.
  • 내부 공기가 존재한다면 bfs를 통해 외부 공기로 다 바꿔준다.

• 시간 + 1

코드

# 2638 치즈

import sys
from collections import deque
input = sys.stdin.readline

'''
cheese 1 _map에 1로 표시 / _visit 에 0 

outer air 2 / _map에 2로 표시 , _visit에 1

inner air 3  / _map,_visit에 둘 다 0
'''


def sol():
    def check_outer_air(r,c):
        q = deque([[r,c]])
        _visit[r][c] = 1

        while q:
            cur_r,cur_c= q.popleft()
            for dr,dc in dirs:
                new_r,new_c = cur_r+dr,cur_c+dc

                # _map이 비어있고, 방문하지 않은 경우 , map에 2로 표시해준다.
                if 0<=new_r<N and 0<=new_c <M and not _map[new_r][new_c] and not _visit[new_r][new_c] :
                    q.append([new_r,new_c])
                    _map[new_r][new_c] = 2



    def melt_cheese(cheeses):
        '''map에서 outer air로 바꾸고 , 방문처리 해주자.'''
        for r,c in cheeses:
            _map[r][c] = 2
            _visit[r][c] = 1
            # 혹시 inner air과 연결되어 있는 경우를 대비...
            check_outer_air(r,c)


    def is_melt_target(r,c):
        count = 0
        for dr,dc in dirs:
            if 0 <= r+dr < N and 0<= c+dc < M and _map[r+dr][c+dc] == 2:
                count += 1
        return True if count >= 2 else False

    def find_cheese():
        candidate_cheese = []
        for r in range(N):
            for c in range(M):
                if _map[r][c] == 1 and is_melt_target(r,c):
                    candidate_cheese.append([r,c])

        return candidate_cheese

    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    hours = 0
    N,M = map(int,input().rstrip().split())
    _map = [list(map(int,input().rstrip().split())) for _ in range(N)]
    _visit = [[0]*M for _ in range(N)]

    check_outer_air(0,0)

    while 1:
        is_exist = find_cheese()
        if not is_exist:
            break


        melt_cheese(is_exist)
        hours += 1

    print(hours)

sol()