백준 2638번: 치즈

BOJ

백준 2638번: 치즈

접근

“치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다.”

처음에 위의 조건을 생각하지 않고 치즈를 기준으로 검색하는 방식으로 코드를 작성했는데 틀렸다.

위의 조건을 만족시키려면 치즈 기준이 아닌 공기 기준으로 dfs 탐색을 돌려야 한다.

Wrong Solution

Correct Solution

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
melted_graph = [[0] * M for _ in range(N)]

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]


def dfs(y, x):
    visit[y][x] = True

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0 <= ny < N and 0 <= nx < M and not visit[ny][nx]:
            if graph[ny][nx] != 0:
                graph[ny][nx] += 1
            else:
                dfs(ny, nx)


cheese = []
for i in range(1, N - 1):
    for j in range(1, M - 1):
        if graph[i][j] == 1:
            cheese.append([i, j])

ans = 0
while cheese:

    visit = [[False] * M for _ in range(N)]

    dfs(0, 0)

    for i in range(len(cheese) - 1, -1, -1):
        y, x = cheese[i]

        if graph[y][x] >= 3:
            graph[y][x] = 0
            cheese.pop(i)
        else:
            graph[y][x] = 1

    ans += 1

print(ans)

참고 사이트

나의 개발능력을 키우기 위한 블로그