π£ λ¬Έμ μ΄ν΄
λ³΄κ΄ ν νλ£¨κ° μ§λλ©΄, μ΅μ ν λ§ν λ€μ μΈμ ν κ³³μ μλ μ΅μ§ μμ ν λ§ν λ€μ μ΅μ ν λ§ν μ μν₯μ λ°μ μ΅κ² λλ€.
νλμ ν λ§ν μ μΈμ ν κ³³μ μΌμͺ½, μ€λ₯Έμͺ½, μ, λ€ λ€ λ°©ν₯μ μλ ν λ§ν λ₯Ό μλ―Ένλ€.
λ©°μΉ μ΄ μ§λλ©΄ ν λ§ν λ€μ΄ λͺ¨λ μ΅λμ§, κ·Έ μ΅μ μΌμλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νλ€.
λλΉ μ°μ νμ(BFS) κΈ°λ²μΌλ‘ νμ΄νλ€.
π νμ΄ κ³Όμ
μμ± μΈμ΄: Python
from collections import deque
def bfs(t_m, t_n, t_box):
day = -1
mx = [-1, 1, 0, 0]
my = [0, 0, -1, 1]
while riped_index:
# ν루 μ© μ¦κ°
day += 1
queue_size = len(riped_index)
for _ in range(queue_size):
x, y = riped_index.popleft()
for k in range(4):
nx = x + mx[k]
ny = y + my[k]
# λ€ λ°©ν₯μ μμΉν ν λ§ν λ€μ΄ μμ λ²μ λ΄μ μκ³ , μ μ΅μ ν λ§ν μΈμ§ 체ν¬
if 0 <= nx < t_n and 0 <= ny < t_m and t_box[nx][ny] == 0:
t_box[nx][ny] = 1
riped_index.append([nx, ny])
# μ¬μ ν μ μ΅μ ν λ§ν κ° λ¨μμμΌλ©΄ -1μ μΆλ ₯, μλλ©΄ μ΅μ λ μ§ μΆλ ₯
answer = sum(temp.count(0) for temp in t_box)
return -1 if answer != 0 else day
m, n = map(int, sys.stdin.readline().split())
box = []
riped_index = deque()
# μ
λ ₯ λ°μ΄ν° 2μ°¨μ λ°°μ΄μ μ½μ΄μ€λ©΄μ,
# 맨 μ²μ μ΅μ ν λ§ν λ₯Ό μ°Ύμμ μμΉλ₯Ό riped_index λ°ν¬μ μ μ₯(νλ₯Ό λ체)
for i in range(n):
row = list(map(int, sys.stdin.readline().split()))
for j in range(m):
if row[j] == 1:
riped_index.append([i, j])
box.append(row)
print(bfs(m, n, box))
π λ°°μ΄ μ
BFS κ°λ μ΄ μ μ©λλ κ²μ μ§κ΄μ μΌλ‘ μ λ³Ό μ μλ λ¬Έμ μλ κ² κ°λ€.
μμ νμ΄μ¬μΌλ‘ ꡬννλ λμ± μ΄λ €μμ λ μ μμλ€. π π π
'Problem_Solving' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ] λ°±μ€ 2606 λ°μ΄λ¬μ€ / λλΉ μ°μ νμ(BFS) (0) | 2020.11.05 |
---|---|
[2020 KAKAO BLIND RECRUITMENT] λ¬Έμμ΄ μμΆ (0) | 2020.09.01 |
[2018 KAKAO BLIND RECRUITMENT] λ€νΈ κ²μ (0) | 2020.08.29 |
[2019 KAKAO BLIND RECRUITMENT] μ€ν¨μ¨ (0) | 2020.08.29 |
[2018 KAKAO BLIND RECRUITMENT] λΉλ°μ§λ (0) | 2020.08.28 |