- 문제 : https://www.acmicpc.net/problem/2636
문제 이해
- 주어진 행렬에서 가장 바깥에 있는 치즈(값이 1인 칸)를 모두 한 번에 지워가면서 (1) 모두 사라지기 전 치즈 칸의 개수와 (2) 다 사라지기 까지의 시간을 구하는 문제다.
- 일단 (1) 모두 사라지기 직전 치즈 칸의 개수를 출력하기 위해 초기 1의 개수(count)를 모두 구한 다음에 한 시간씩 치즈가 사라질 때마다 그 개수를 count에서 빼주면서 진행하면 된다. 모두 사라졌을 때는 count를 감소 시키는 단계가 없기 때문에 그대로 count를 출력하면 된다.
- (2) 시간은 bfs를 진행하는 횟수로 세면 된다.
- 일단 바깥 치즈의 위치를 큐에 저장한 뒤, 탐색이 끝나면 그때 큐에 저장한 치즈를 모두 제거한다. (그때그때 치즈를 제거하면 바깥에 있지 않은 다른 치즈가 제거될 수 있기에 바깥 치즈를 모두 모았다가 한 번에 제거해야 한다)
- 대충 이렇게 까지는 그려졌는데, 가장 어려웠던 부분이 바깥 치즈의 위치를 구하는 것이었다. 1을 기준으로 근처에 0이 있는 걸로 하면, 내부에 구멍이 있는 경우도 해당되기 때문에 어떻게 해야할지 감이 안 잡혔다.
- 그래서 풀이를 찾아보았더니, 값이 0인 (0, 0)에서 시작해 0을 기준으로 탐색을 하면 된다는 거다. 0을 기준으로 시작해 움직이다가 만나는 1은 바깥에 있는 값이다. 그리고 0을 만나면 이를 큐에 넣어서 탐색을 진행하면 된다. 바깥에 있는 1의 값은 melt에 넣고, 0은 queue에 넣어서 bfs를 진행하면 된다.
- 그 외는 bfs 기본 로직이다.
-> 가장 바깥에 있는 1을 구하는 방법 기억하자!!!!
정답 풀이
from collections import deque
def bfs():
queue = deque() # 값이 0인 좌표
queue.append([0, 0])
melt = deque() # 가장 바깥에 있는 치즈 좌표
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny] :
visit[nx][ny] = 1
if cheese[nx][ny] == 0:
queue.append([nx, ny])
elif cheese[nx][ny] == 1:
melt.append([nx, ny])
for x, y in melt:
cheese[x][y] = 0
return len(melt)
n, m = map(int, input().split())
cheese = []
count = 0 # 나중에 모두 없어지기 한 시간 전 치즈 칸 개수 세기 위함
time = 1
for i in range(n):
data = list(map(int, input().split()))
cheese.append(data)
for j in range(m):
if data[j] == 1:
count += 1
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
while True:
visit = [[0] * m for _ in range(n)]
melt_count = bfs()
count -= melt_count
if count == 0:
print(time)
print(melt_count)
break
time += 1
참고 블로그
'백준 > 구현' 카테고리의 다른 글
| [구현/백준] 15662번: 톱니바퀴(2) (0) | 2023.10.02 |
|---|---|
| [구현/백준] 15686번 : 치킨 배달 (2) | 2023.10.02 |
| [구현/백준] 7490번 : 0 만들기 (0) | 2023.09.14 |
| [구현/백준] 14719번 : 빗물 (0) | 2023.09.13 |
| [구현/백준] 20055번 : 컨베이어 벨트 (0) | 2023.09.12 |
