백준 2636 치즈

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

2636번: 치즈

📌 해결과정

정말 삽질을 길게 했던 문제다,, 

 

우선 탐색을 하기 전 구멍이 뚫린 영역을 찾아서 그 영역을 2로 바꾼다.

그 다음 탐색을 하는 과정에서 4방향 중에 공기와 닿는 치즈가 있으면, 즉 4방향 중에 0인 좌표가 있으면 녹이려고 했다.

 

하지만 이 과정은 문제가 많다.

구멍을 뚫린 영역만 찾아서 2로 바꾸는게 정말 쉽지 않다.

 

그래프의 각 좌표를 방문 하다가, 값이 1인 좌표를 만난다 -> 

방문해서 4방향 중에서 0 인 좌표가 있는지 찾는다 -> 

0인 좌표가 있으면 값이 1이였던 좌표를 0으로 변경하고, 방문 표시 해주고, que 에 추가한다 

 

그림으로 표시하면 이렇다

 

 

따라서, 다른 방법으로 풀어야 했다.

그래프를 탐색하다가 0을 만난다. 0을 만난다는 것은 주위 4방향 중에 1인 좌표(치즈가 있는 장소)가 있으면 녹일수 있다는 것을 뜻한다->

그리고 각 4방향에 대해서 

0을 만난 경우 : 방문 표시를 해주고, que 에 추가한다

1을 만난 경우 : 방문 표시를 해주고, 녹이고 (값을 0으로 변경하고), que 에 추가하지 않는다

"que 에 추가하지 않는다" 이게 문제의 핵심이였다

1을 만나면 que 에 추가하지 않고 0으로 변경하고 방문 표시만 해줘야 한다,

만약 치즈가 있는 좌표를 que 에 추가 한다면 위 그림 처럼 안쪽의 치즈도 녹이게 되는 상황이 발생한다

 

이렇게 하면 1시간에 겉에 있는 치즈만 녹일 수 있다.

 

그리고 더이상 녹일 치즈가 없을 때 까지 bfs 를 호출 하는데, 호출 할때마다 visited 배열을 초기화 해줘야 했다.

한시간 전에 녹았던 치즈는 공기가 되어서 이제 안쪽 치즈를 녹일수 있다.

여기서 visited 배열을 초기화 하지 않으면 한시간 전에 방문 처리가 됐기 때문에, que 에 추가되지 못하고 안쪽 치즈를 녹일 수 없다.

 

이 2가지가 문제를 푸는 핵심 키워드 였다..!

1. 치즈가 있었던 좌표는 que 에 추가하지 않는다

2. 다시 bfs 호출하기전에 visitied 배열을 초기화 한다

 

지금까지 bfs 를 통해서 탐색 문제를 풀었을 때는 좌표 조건만 맞으면 무조건 que 에 추가하고 다음 탐색을 하는 방식으로 풀었었는데,

이 문제를 통해서 좌표 조건이 맞더라도 값에 따라서 que 에 추가할지 말지를 결정해줘야 하는 상황도 발생할 수 있음을 알게 됐다.

다음에는 이런 문제를 깔끔하고 빠른 시간내에 풀고싶다! 😂😂😂😂😂

 

📌 코드

from collections import deque
import sys

input = sys.stdin.readline


def bfs(x, y):
    que = deque()
    que.append((x, y))
    visited[x][y] = 1

    melt_count = 0

    while que:
        x, y = que.popleft()

        for (dx, dy) in DIRECTION:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < row and 0 <= ny < col and not visited[nx][ny]:
                visited[nx][ny] = 1
                if cheezes[nx][ny] == 0:
                    que.append((nx, ny))
                # * 가장자리가 1이다, que 에 추가하지 않음 => 추가하면 안쪽으로 들어가서 또 녹임
                # ! 가장자리 1을 방문 표시를 해주고 녹이지만, 다시 que 에 추가하지 않는 것이 핵심
                elif cheezes[nx][ny] == 1:
                    cheezes[nx][ny] = 0
                    melt_count += 1

    return melt_count


if __name__ == "__main__":
    row, col = map(int, input().split())
    cheezes = [list(map(int, input().split())) for _ in range(row)]
    DIRECTION = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    times = 0
    melt_cheezes = []

    while True:
        # ! 시간 지날 때 마다 visited 초기화 해야함, 0 으로 인해서 녹을 치즈가 생기게 해줘야함!
        visited = [[0] * col for _ in range(row)]

        cnt = bfs(0, 0)
        if cnt == 0:
            break

        melt_cheezes.append(cnt)
        times += 1

    print(times)
    print(melt_cheezes[-1])