IT-garden

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

예제 입력과 출력

정답

import sys
from collections import deque
import copy
input = lambda : sys.stdin.readline().strip()

h,w=map(int,input().split()) #h세로 w가로
a=[list(map(int,input().split())) for i in range(h)]
b=copy.deepcopy(a) 
ch=[[-1]*w for i in range(h)]

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

li=[]

def air(s1,s2):
    de=deque()
    de.append([s1,s2])
    b[s1][s2] = -1
    
    while de:
        x,y=de.popleft()

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

            if 0 <= nx < h and 0 <= ny < w:
                if a[nx][ny] == 0 and ch[nx][ny] == -1:
                    b[nx][ny] = -1
                    ch[nx][ny] = 0
                    de.append([nx,ny])

def air2(s1,s2):
    ch=[[-1]*w for i in range(h)]
    de=deque()
    de.append([s1,s2])
    b[s1][s2] = -1
    
    while de:
        x,y=de.popleft()

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

            if 0 <= nx < h and 0 <= ny < w:
                if (b[nx][ny] == 0 or b[nx][ny] in li) and ch[nx][ny] == -1:
                    b[nx][ny] = -1
                    ch[nx][ny] = 0
                    de.append([nx,ny])
     
def cheese(s1,s2,c):
    global answer
    
    for i in range(4):
        nx = s1 + dx[i]
        ny = s2 + dy[i]

        if 0 <= nx < h and 0 <= ny < w:
            
            if b[nx][ny] in li:
                b[s1][s2] = c
                answer += 1
                break
air(0,0) 
c= 1
li.append(-1)

while True:
    c += 1
    answer=0
    for i in range(h):
        for j in range(w):
            if b[i][j] != -1 and b[i][j] not in li:
                cheese(i,j,c)
                
    li.append(c)
    one = 0
    for i in b:
        one += i.count(1)

    if one == 0:
        print(c-1)
        print(answer)
        break

    air2(0,0)

1. 입력받은 리스트 a를 b로 복사합니다.

2. 함수 air를 통해 공기(-1), 구멍(0)과 치즈(1)를 분리합니다.
3. 함수 cheese를 통해서 치즈에서 공기와 접한 곳들을 확인해 값 c를 넣어줍니다. c는 걸린시간 +1
4. 리스트 b에서의 치즈의 개수를 확인합니다.
4-1. 치즈의 개수가 없다면 치즈가 모두 녹는데 걸린 시간과 모두 녹기 한 시간 전에 남아있는 치즈의 개수를 확인해 출력합니다.
4-2. 치즈가 아직 남아있다면 함수 air2를 통해 치즈가 녹으면서 늘어난 곳을 확인해 공기로 바꿔줍니다.
5. 3와 4과정을 4-1이 될때까지 반복합니다.

위의 풀이과정은 비효율적인 코드입니다.

import sys
from collections import deque
input = lambda : sys.stdin.readline().strip()

h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
c=0
re=[]

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

def bfs():
    de=deque()
    de.append([0,0])
    ch=[[-1]*w for i in range(h)]
    ch[0][0]=0

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

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

            if 0 <= nx < h and 0 <= ny < w:
                if ch[nx][ny] == -1:
                    if a[nx][ny] >= 1:
                        a[nx][ny] += 1
                    else:
                        ch[nx][ny] = 0
                        de.append([nx,ny])

while True:
    bfs()
    cht = 0
    cou=0
    
    for i in range(h):
        for j in range(w):
            if a[i][j] >= 2:
                a[i][j] = 0
                cou += 1
                cht = 1
                
    if cht == 1:
        c += 1
        re.append(cou)
    else:
        break

print(c)
print(re.pop())

1. bfs를 통해 인접한 칸이 치즈면 치즈를 1 증가하고 공기칸이면 방문확인을 해주고 이동합니다.
2. 리스트 a에서 2이상인 것은 치즈가 녹았으니 0으로 바꾸고 해당 시간에 녹인 치즈의 수를 구해 리스트에 저장합니다.
3. 위의 과정을 치즈가 녹을때까지 반복하고 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈의 개수를 구해 출력합니다.

백준 알고리즘 2636번 : https://www.acmicpc.net/problem/2636