https://www.acmicpc.net/problem/2636
-
문제
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오. -
입력
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다. -
출력
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
BFS인건 감이 왔는데 이걸 한번에 해치우는 BFS 함수를 만드려니까 어지러웠다.
그래서 블로그를 참고,,,,
한번 가장자리를 없앨때마다 즉, 한시간에 한번씩 BFS를 다시 호출하는 방법이 제일 간단해보여서 그걸로 해결했고, 난 왜 맨날 행과 열이 헷갈릴깡... 이제 걍 외워야겠당.
암튼 생각보다 간단한 문제였다 !!
아 글구 마지막에 다 녹기 한시간 전 가장자리 개수 출력할때 ans[-2] 해주는게 아주 깔끔해보였당
그리고 deque에 두개 넣어줄때 괄호 묶어주는거 잊지말기!!
import collections
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
def bfs(): # 중요) 가장자리 한번 녹을때마다 한번 호출
queue = collections.deque()
queue.append((0,0)) # 처음부터 시작
visited = [[0] * m for _ in range(n)] # 체크
count = 0
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m: # 자꾸 행과열 헷갈림 ㅜㅜㅜㅜㅜ
if lst[nx][ny] == 0 and visited[nx][ny] == 0: # 가장자리가 아닌 바깥
visited[nx][ny] = 1 # 체크하고
queue.append((nx, ny)) # 계속 가야하니까 큐에 넣는다
elif lst[nx][ny] == 1 and visited[nx][ny] == 0: # 가장자리면
lst[nx][ny] = 0 # 녹인다
visited[nx][ny] = 1 # 체크
count += 1 # 녹는개수 즉 가장자리 세기
return count
ans = []
time = 0
while True:
cnt = bfs()
ans.append(cnt)
if cnt == 0: # 가장자리가 없으면, 즉 다녹으면
break
time += 1
print(time)
print(ans[-2]) # 뒤에서 두번째, 즉 녹기 바로 전