문제
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
<그림 1> 원래 치즈 모양
다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
<그림 2> 한 시간 후의 치즈 모양
<그림 3> 두 시간 후의 치즈 모양
<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
접근방법
1. 앞으로 굴러도 뒤로 굴러도 옆으로 굴러도 그래프 문제 (BFS)
2. 공기와 닿아있는 부분이 녹아야 하기 떄문에 경계면을 체크합시다
3. 탐색 종료는 어떻게 할까요 더이상 녹일 치즈가 없을 때 합시다.
실패한 풀이
from collections import deque
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
def bfs(r, c):
cheese2 = 1
border = set()
visit = [[0] * m for _ in range(n)]
Q = deque()
Q.append((r, c))
visit[r][c] = 1
while Q:
r, c = Q.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < m and visit[nr][nc] == 0:
visit[nr][nc] = 1
if arr[nr][nc] == 1:
cheese2 += 1
Q.append((nr, nc))
if arr[nr][nc] == 0:
border.add((r, c))
for cr, cc in border:
arr[cr][cc] = 0
return cheese2
# 세로 가로
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
# visit = [[0] * m for _ in range(n)]
# 소모시간
hour = 1
flag = True
border = set()
while flag:
cheese = 0
# bfs 탐방 확인용
cnt = 0
for r in range(n):
for c in range(m):
if arr[r][c] == 1:
cheese += bfs(r, c)
cnt = 1
hour += 1
if cnt == 0:
flag = False
print(hour)
print(cheese)
문제점
1. 우리가 녹이고 싶은 치즈는 밖의 공기와 닿아있는 치즈 ( 안의 공기는 괜찮음 )
=> 위의 코드는 경계을 체크하는 기준을 0을 만났을 때 로 설정했다
=> 속에 있는 공기까지 체크해서 경계면으로 보고 녹여버린다. 속에 있는 공기는 괜찮다며???
2. 1을 만났을때 bfs 탐색을 시작한다
=> 테두리만 녹여버리기 때문에 치즈는 배열에 치즈는 아직도 잔뜩 남은 상태
=> 그런데 계속 탐색해버린다 => 치즈가 계속 누적됨
=> 원래 있던 치즈보다 많은 치즈가 생겨버리는 문제
통과 코드
from collections import deque
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
def bfs():
melt = 0
border = []
visit = [[0] * m for _ in range(n)]
Q = deque()
Q.append((0, 0))
visit[0][0] = 1
while Q:
r, c = Q.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < m and visit[nr][nc] == 0:
visit[nr][nc] = 1
if arr[nr][nc] == 0:
Q.append((nr, nc))
if arr[nr][nc] == 1:
border.append((nr, nc))
for cr, cc in border:
melt += 1
arr[cr][cc] = 0
return melt
# 세로 가로
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
# visit = [[0] * m for _ in range(n)]
# 소모시간
hour = 0
flag = True
cheese = 0
while flag:
# bfs 탐방 확인용
cnt = bfs()
if cnt > 0:
cheese = cnt
hour += 1
if cnt == 0:
flag = False
print(hour-1)
print(cheese)
개선점
1. 경계면 체크의 개념을 바꾸자
=> 안의 공기(치즈로 쌓여있는 공기)를 무시하기 위해선 1을 경계로 생각하자
=> 0을 만났을때 위치를 이동하게 되면 1로 둘러 쌓여있는 경우엔 더이상 안쪽으로 들어가지 않는다.
2. 그냥 처음부터 끝까지 가보자
=> 시작위치를 0,0 으로 고정하고 탐색하면 bfs 한번에 모든 배열을 탐색할 수 있다
=> 치즈가 중첩되는걸 막아줄 수 있음!
느낀점
테두리를 체크해야 한다는걸 생각하는게 80%는 차지하는 문제인 것 같다.
테두리 체크 자체는 생각했지만 이전에 풀었던 다리만들기나, 기존 bfs 에서 0을 무시하고 1을 경로로 삼는 버릇때문에
평소 습관처럼 문제를 풀다가 낭패를 본 것 같다. 그래도 테두리 체크가 필요하다는 생각을 했으니까 다행
한시간정도 지나서 해설을 대충 훑어보고 테두리 체크 방식을 바꾸고 바로 해결했다.
역발상이 필요하다!
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 26215 눈 치우기 (파이썬) (0) | 2023.01.18 |
---|---|
백준 1197 최소 스패닝 트리 (파이썬) (0) | 2022.10.28 |
백준 5014 스타트 링크 (파이썬) (0) | 2022.10.13 |
백준 8979 올림픽 (파이썬) (0) | 2022.09.26 |
백준 10971 외판원 순회 2 (파이썬) (조합 생성방법) (0) | 2022.09.24 |