[백준] 2636 : 치즈 / python

1. 문제 설명

2638번: 치즈

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다.

단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다.

이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다.

그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서

적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다.

따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면

C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

 

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다.

그러므로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다.

그러나 한 시간 후, 이 공간으로 외부공기가 유입되면

<그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

 

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다.

그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고,

치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

 

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

 

2. 첫번째 풀이 전 계획과 생각

적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다.

 

🤔  2변 이상 실내온도의 공기와 접촉한 것을 어떻게 체크해줄 수 있을까?

→ 해당 원소에서 상하좌우 탐색했을 때, 0이 2개 이상이면, 실내온도의 공기와 접촉한 것이다.

 

N과 M의 가운데에서 상하좌우로 탐색해주면서, 0이 2개 이상인 경우면 치즈를 없앤다.

모든 정점을 방문하는 것이 주요한 문제이므로, DFS나 BFS 중 어느 것을 사용해도 상관없다.

 

1. C인 곳을 찾자. 시작점으로 둔다.
2. 시작점에서 BFS로 탐색한다.
3. 큐가 빌때까지 아래의 행동을 반복한다.
   • 시작점의 상하좌우로 이동한다.
     • 다음점이 0≤ nx, ny ≤ N, M이면
       • 0인지 체크한다. →
         • 0이면, contacted_grid_count += 1
         • 1이면, 큐에 넣어준다.
   • 범위 벗어나면, continue
   • 한번 상하좌우 탐색했을 때, 0이 2개이상이면, 해당 치즈는 없앤다.

 

🤔  전체 그래프가 0인지 체크해주려면

이중 반복문을 계속 반복해서 돌리는 것인가? → 3중 반복문 사용 (너무 복잡하다.)

 

3. 첫번째 풀이

# 1. C인 곳을 찾자. 시작점으로 둔다.
# 2. 시작점에서 BFS로 탐색한다.
# 3. 큐가 빌때까지 아래의 행동을 반복한다.
    # 1) 시작점의 상하좌우로 이동한다.
        # 다음점이 0≤ nx, ny < N, M이면
            # 0인지 체크한다. →
                # - 0이면, contacted_grid_count += 1
                # - 1이면, 큐에 넣어준다.
    # 2) 범위 벗어나면, continue
    # 3) 한번 상하좌우 탐색했을 때, 0이 2개이상이면, 해당 치즈는 없앤다.

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

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    # 현재 노드를 방문 처리
    visited[y][x] = 1
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        y, x = queue.popleft()

        contacted_grid_count = 0
        for dy, dx in direction:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == 0:
                    contacted_grid_count += 1
                else:
                    if visited[ny][nx] == 0:
                        queue.append((ny, nx))
                        visited[ny][nx] = 1
        if contacted_grid_count >= 2:
            graph[y][x] = 0

N, M = map(int, input().split())
graph = [input().strip() for _ in range(N)]
visited = [[0] * M for _ in range(N)]
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
hour = 0

while True:
    count = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == '1':
                bfs(i, j)
                count += 1
                hour += 1
                break
    if count == 0:
        break
print(hour)

 

4. 풀이하면서 막혔던 점과 고민

🤔  break가 안에 있으면, 전체 반복문을 없앤다.

→ 그러므로, 전체 그래프가 0인지 체크해주려면 3중 반복문 한꺼번에 사용하는 것이 아니라,

함수를 만들어서 분리해주어야겠다.

→ 또한, 시작점은 항상 (0,0)두어 탐색 하면 되므로, 1을 찾는 이중반복문을 사용할 필요가 없다.

 

😛  앗! 그리고 공기 접촉의 기준은 외부 공기와 접촉만 따진다. 내부 공기는 따지지 않는다는 조건을 빼먹었다.

⇒ 다시 알고리즘을 짜자.

 

5. 두번째 풀이 전 계획과 생각

외부공기, 내부공기 분리 어떻게 하면 좋을까?

1. 겉면에서 0인 친구들을 vertex로 생각하여, bfs 탐색한다. (0,0)에서 시작점을 두자.
2. 외부 공기를 -1로 만들어주면 된다.

 

계획

1. 다 녹았는지 check 한다.
   1. 다 녹았다면, 시간을 출력하고 프로그램 종료한다.
   2. 다 녹지 않았다면 시작점을 보내며, 2번으로 가자.
2. bfs 탐색해서 외부 공기를 만든다.
   1. (0,0)에서 시작점을 두자. 0인 vertex들을 탐색하면서 -1로 만들자.
3. bfs 탐색해서 녹이자.
   1. 1이 있는 곳을 찾아 시작점을 두자. 1인 vertex들을 탐색하면서 상하좌우가 -1이 2개가 있으면, 녹인다.

• 다 녹았는지 check하는 함수 is_melt()
• 탐색하며, 외부공기 만드는 함수 make_air()
• 탐색하며, 녹이는 함수 melt_cheese()
• 외부공기, 방문처리 초기화 하는 함수 init()

 

6. 두번째 풀이

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

N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))
visited = [[0] * M for _ in range(N)]
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
hour = 0

def init():
    for i in range(N):
        for j in range(M):
            if graph[i][j] == -1:
                graph[i][j] = 0
            if visited[i][j] == 1:
                visited[i][j] = 0

def melt_cheese(y, x):
    queue = deque()
    queue.append((y, x))
    visited[y][x] = 1

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

        contacted_grid_count = 0
        for dy, dx in direction:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == -1:
                    contacted_grid_count += 1
                else:
                    if graph[ny][nx] == 1 and visited[ny][nx] == 0:
                        queue.append((ny, nx))
                        visited[ny][nx] = 1
        if contacted_grid_count >= 2:
            graph[y][x] = 0

def make_outair():
    visited = [[0] * M for _ in range(N)]
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = 1

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

        for dy, dx in direction:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == 0 and visited[ny][nx] == 0:
                    queue.append((ny, nx))
                    graph[ny][nx] = -1
                    visited[ny][nx] = 1

def get_meltpos():
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                return i, j
    else:
        return None

while True:
    pos = get_meltpos()
    if pos == None:
        print(hour)
        break

    make_outair()
    melt_cheese(pos[0], pos[1])
    hour += 1
    init()

 

7. 풀이하면서 막혔던 점과 고민

예시에 있는 입력을 넣어주면, 출력이 맞게 나왔지만, 시간 초과가 났다.

 

🤔 시간복잡도를 어디서 줄여줄 수 있을까?

 

💡 외부 공기 체크해 줄 때, 녹일 치즈 후보를 queue에 저장한다.

그러면, 녹일 때 치즈를 찾기 위해 그래프 전체 탐색해 줄 필요없이, 외부 공기에 있는 치즈만 체크해주면 된다.

 

⇒ make_outair

외부 공기 일때, 인접한 부분이 치즈면

→ 해당 visit 값을 1로 바꾸고, 녹일 치즈 후보 queue에 저장해놓는다.

바로 공기층과 맞닿은 가장 바깥부분의 치즈이기 때문이다.

 

⇒ melt_cheese

큐에서 치즈를 꺼내서, 상하좌우 -1이 2개 이상인지 체크해준다.

 

8. 최종 풀이

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

N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))
visited = [[0] * M for _ in range(N)]
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
hour = 0
cheese_queue = deque()

def init():
    for i in range(N):
        for j in range(M):
            if graph[i][j] == -1:
                graph[i][j] = 0
            if visited[i][j] == 1:
                visited[i][j] = 0

def melt_cheese():
    while cheese_queue:
        y, x = cheese_queue.popleft()

        contacted_grid_count = 0
        for dy, dx in direction:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == -1:
                    contacted_grid_count += 1
        if contacted_grid_count >= 2:
            graph[y][x] = 0

def make_outair():
    visited = [[0] * M for _ in range(N)]
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = 1

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

        for dy, dx in direction:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == 1:
                    cheese_queue.append((ny, nx))
                    visited[ny][nx] = 1
                if graph[ny][nx] == 0 and visited[ny][nx] == 0:
                    queue.append((ny, nx))
                    graph[ny][nx] = -1
                    visited[ny][nx] = 1

def get_meltpos():
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                return i, j
    else:
        return None

while True:
    pos = get_meltpos()
    if pos == None:
        print(hour)
        break

    make_outair()
    melt_cheese()
    hour += 1
    init()

 

9. 풀이 후 알게된 개념과 소감

• 다른 조건일 경우, 구분해서 같이 처리하는 경우도 있지만, 아예 분리해서 접근하는 경우도 있다.
• 조건을 보면, 항상 외부 공기가 존재한다.
  → 조건을 통해 (0, 0)에서 항상 시작하여, 외부 공기 먼저 탐색해야겠다는 접근에 갈 수 있었다.
• 외부 공기 만날 때, 외부 공기와 접촉하는 치즈를 만나게 된다. 이때, 큐에 넣어준다.
  그러면, 다시 치즈를 탐색하기 위해, 그래프 전체 탐색할 필요 없다.