입력값 : N , M 행 열 (최대길이 100) 치즈 없는 칸 0, 치즈 있는 칸 1로 주어집니다.
유의해야 할 점 : 치즈가 공기와 접촉하게 되면 접촌된 칸은 한 시간이 지나면 없어진다. 치즈의 구멍 안에는 공기가 없지만, 녹아서 뚫리면 공기가 들어간다.
출력값 : 치즈가 모두 녹아서 없어지는 시간 모두 녹기 전 남아있던 치즈조각의 칸 갯수
2. 문제 풀이 법
사용한 방법: 1. bfs 2. 4방향
제일 위에 정의하는거 : 각 시간당 남아있는 치즈의 갯수를 저장할 배열 : cz'
각 시간마다 실행되는 bfs 함수에서 하는 일 : visited 를 초기화해줍니다. bfs(0,0)으로 불러서 바깥만 탐색 -> 치즈가 뚫리면 탐색하면서 내부도 이어 줄 수 있습니다. 탐색한 바깥마다 4방향 탐색 해서 치즈 있는지 없는지 보게됩니다. 치즈 있을 경우 visited 체크 해 주고 0 으로 바꿔줌으로서 새로운 바깥이 됩니다.
다 녹기전 치즈가 차지하고 있는 칸의 수를 구해야하기때문에 한 시간이 지날 때 마다 치즈 양을 기록해줍니다. 치즈 양이 0 일때 멈추고 결과를 출력하게 됩니다.
3. 어려웠던 점
언제 dfs 써야하는지 bfs 써야 하는지 잘 모르겠다. 강사님이 말씀하시길, 그냥 탐색하는건 dfs 하면 된댔는데 이건 왜 bfs로 풀었지? 나도 내가 이해가 안간다.
N, M = map(int,input().split())
cz=[]
cnt = 0
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x,y):
q = []
q.append([x,y])
visited[y][x] = 1
while q:
t = q.pop(0)
tx = t[0]
ty = t[1]
for k in range(4):
temp_x = tx + dx[k]
temp_y = ty + dy[k]
if 0 <= temp_x < M and 0 <= temp_y < N:
if visited[temp_y][temp_x] == 0:
if cz[temp_y][temp_x] != 1:
for r in range(4):
cz_x = temp_x + dx[r]
cz_y = temp_y + dy[r]
if 0 <= cz_x < M and 0 <= cz_y < N:
if cz[cz_y][cz_x] == 1:
cz[cz_y][cz_x] = 0
visited[cz_y][cz_x] = 1 # g헷갈려
visited[temp_y][temp_x] = 1
q.append([temp_x,temp_y])
for i in range(N):
cz.append(list(map(int,input().split())))
for i in range(M):
for j in range(N):
cnt += cz[j][i]
cz_list = [cnt]
while True:
flag = 0
visited = [[0 for _ in range(M)] for _ in range(N)] # 새로고침하는거 어디서할지
bfs(0,0)
for i in range(M):
for j in range(N):
if cz[j][i] == 1:
flag += 1
cz_list.append(flag)
if flag == 0:
break
print(len(cz_list)-1)
print(cz_list[-2])
