[BOJ] 2636. 치즈

문제

치즈 (https://www.acmicpc.net/problem/2636)

풀이

1. 초기접근

• 문제조건 해석
  • 한 step 단위로, 판의 상태가 달라진다.
    • DFS, BFS 문제다.
  • 가장자리의 치즈만 트래킹해서 처리해야한다.
    • DFS 로 풀 수 있겠다.
• 알고리즘
  • 기본적인 아이디어는 이렇다.
    • 먼저 치즈가 있는부분(1)을 찾는다.
    • 해당 좌표에서 상하좌우의 연결된 1들을 쭉 탐색(DFS) 한다.
    • 탐색하는 동안, 해당 좌표가 가장자리이면, 탐색을 마칠 때, 치즈(1)가 아닌 공기(0)로 상태를 바꿔준다.
    • 해당 좌표가 가장자리인지 아닌지 알려면, 좌표기준 상하좌우를 다 둘러보아 공기(0)이 있는지 확인한다.
  • 이 때, 공기를 좀 구분해줄 필요가 있는데, 가장자리임을 알 수 있는 공기는 바깥공기다.
    • 따라서, 치즈 내부와 외부 공기로 나눌 수 있는데, 외부는 -1, 내부는 0으로 바꾼다.
    • 바꾸는 방법 역시 DFS를 사용한다.
    • (0, 0)은 항상 0 이므로, (0, 0)에 연결된 0들을 쭉 탐색하며 -1로 바꿔주면 된다.
• 코드

import sys
sys.setrecursionlimit(10**8)

dxs = [-1, 0, 1, 0]
dys = [0, 1, 0 ,-1]

def make_label(x, y, visited):
    # 외부 0과 치즈 내부 0을 구분하여 board를 재구성.
    # 외부 0은 -1로 바꿔줌.
    visited.add((x, y))
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        if nx >= 0 and nx < n and ny >= 0 and ny < m and (nx, ny) not in visited\
            and (board[nx][ny] == 0 or board[nx][ny] == -1):
            make_label(nx, ny, visited)
    board[x][y] = -1

def melt(x, y, visited):
    visited.add((x, y))

    # 현재 위치가 치즈의 사이드인지 확인
    is_side = False
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        if board[nx][ny] == -1:
            is_side = True
            break

    # 사이드인 경우, dfs 진행
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        if nx >= 0 and nx < n and ny >= 0 and ny < m and (nx, ny) not in visited\
            and board[nx][ny] == 1:
            melt(nx, ny, visited)

    # 탐색을 마치고 나갈 때, 현재좌표를 녹은상태로 만들기
    if is_side:
        board[x][y] = -1

    return visited


n, m = list(map(int, input().split()))
board = [list(map(int, input().split())) for _ in range(n)]

melt_all, time, visited  = False, 0, None
while not melt_all:
    make_label(0, 0, set())
    visited = set()

    for i in range(n):
        for j in range(m):
            if board[i][j] == 1 and (i, j) not in visited:
                visited |= melt(i, j, set())

    time += 1

    # 다 녹았는지 체크
    melt_all = True
    for i in range(n):
        for j in range(m):
            if board[i][j] == 1:
                melt_all = False
print(time)
print(len(visited))