ν λ§ν
π λ¬Έμ
λ¬Έμ
μ² μμ ν λ§ν λμ₯μμλ ν λ§ν λ₯Ό 보κ΄νλ ν° μ°½κ³ λ₯Ό κ°μ§κ³ μλ€.
ν λ§ν λ μλμ κ·Έλ¦Όκ³Ό κ°μ΄ 격μ λͺ¨μ μμμ μΉΈμ νλμ© λ£μ΄μ μ°½κ³ μ 보κ΄νλ€.μ°½κ³ μ 보κ΄λλ ν λ§ν λ€ μ€μλ μ μ΅μ κ²λ μμ§λ§, μμ§ μ΅μ§ μμ ν λ§ν λ€λ μμ μ μλ€.
λ³΄κ΄ ν νλ£¨κ° μ§λλ©΄,
μ΅μ ν λ§ν λ€μ μΈμ ν κ³³μ μλ μ΅μ§ μμ ν λ§ν λ€μ μ΅μ ν λ§ν μ μν₯μ λ°μ μ΅κ² λλ€.
νλμ ν λ§ν μ μΈμ ν κ³³μ μΌμͺ½, μ€λ₯Έμͺ½, μ, λ€ λ€ λ°©ν₯μ μλ ν λ§ν λ₯Ό μλ―Ένλ€.
λκ°μ λ°©ν₯μ μλ ν λ§ν λ€μκ²λ μν₯μ μ£Όμ§ λͺ»νλ©°, ν λ§ν κ° νΌμ μ μ λ‘ μ΅λ κ²½μ°λ μλ€κ³ κ°μ νλ€.
μ² μλ μ°½κ³ μ 보κ΄λ ν λ§ν λ€μ΄ λ©°μΉ μ΄ μ§λλ©΄ λ€ μ΅κ² λλμ§, κ·Έ μ΅μ μΌμλ₯Ό μκ³ μΆμ΄ νλ€.ν λ§ν λ₯Ό μ°½κ³ μ 보κ΄νλ 격μλͺ¨μμ μμλ€μ ν¬κΈ°μ
μ΅μ ν λ§ν λ€κ³Ό μ΅μ§ μμ ν λ§ν λ€μ μ λ³΄κ° μ£Όμ΄μ‘μ λ,
λ©°μΉ μ΄ μ§λλ©΄ ν λ§ν λ€μ΄ λͺ¨λ μ΅λμ§, κ·Έ μ΅μ μΌμλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νλΌ.
λ¨, μμμ μΌλΆ μΉΈμλ ν λ§ν κ° λ€μ΄μμ§ μμ μλ μλ€.μ λ ₯
첫 μ€μλ μμμ ν¬κΈ°λ₯Ό λνλ΄λ λ μ μ M,Nμ΄ μ£Όμ΄μ§λ€.
Mμ μμμ κ°λ‘ μΉΈμ μ, Nμ μμμ μΈλ‘ μΉΈμ μλ₯Ό λνλΈλ€. λ¨, 2 ≤ M,N ≤ 1,000 μ΄λ€.
λμ§Έ μ€λΆν°λ νλμ μμμ μ μ₯λ ν λ§ν λ€μ μ λ³΄κ° μ£Όμ΄μ§λ€.
μ¦, λμ§Έ μ€λΆν° Nκ°μ μ€μλ μμμ λ΄κΈ΄ ν λ§ν μ μ λ³΄κ° μ£Όμ΄μ§λ€.
νλμ μ€μλ μμ κ°λ‘μ€μ λ€μ΄μλ ν λ§ν μ μνκ° Mκ°μ μ μλ‘ μ£Όμ΄μ§λ€.
μ μ 1μ μ΅μ ν λ§ν , μ μ 0μ μ΅μ§ μμ ν λ§ν , μ μ -1μ ν λ§ν κ° λ€μ΄μμ§ μμ μΉΈμ λνλΈλ€.ν λ§ν κ° νλ μ΄μ μλ κ²½μ°λ§ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
μΆλ ₯
μ¬λ¬λΆμ ν λ§ν κ° λͺ¨λ μ΅μ λκΉμ§μ μ΅μ λ μ§λ₯Ό μΆλ ₯ν΄μΌ νλ€.
λ§μ½, μ μ₯λ λλΆν° λͺ¨λ ν λ§ν κ° μ΅μ΄μλ μνμ΄λ©΄ 0μ μΆλ ₯ν΄μΌ νκ³ ,
ν λ§ν κ° λͺ¨λ μ΅μ§λ λͺ»νλ μν©μ΄λ©΄ -1μ μΆλ ₯ν΄μΌ νλ€.
π§ νμ΄
νμ΄
# [νμ΄μ¬] λ°±μ€ 7576λ² λ¬Έμ : ν λ§ν
import sys # sys λΆλ¬μ€κΈ°
from collections import deque # deque λΆλ¬μ€κΈ°
m, n = map(int, input().split()) # m, n μ
λ ₯ λ° ν λΉ
storage = [list(map(int,input().split())) for _ in range(n)] # ν λ§ν μ°½κ³ μ
λ ₯ λ° ν λΉ
dx = [1, -1, 0, 0] # x μ΄λ μ’ν
dy = [0, 0, 1, -1] # y μ΄λ μ’ν
q = deque() # λΉ queue ν λΉ
dis = [[0] * m for _ in range(n)] # 거리λ₯Ό λ΄κΈ° μν dis λ°°μ΄ ν λΉ
check1 = 0 # μ μ΅μ ν λ§ν κ° μλμ§ νμΈνκΈ° μν check1 ν λΉ
for c1 in storage: # storageμ κ° νλ§λ€
if 0 not in c1: # μ μ΅μ ν λ§ν κ° μλ€λ©΄ (0)
check1 += 1 # check1 1μ© μ¦κ°
if check1 == n: # check1κ³Ό nμ ν¬κΈ°κ° κ°λ€λ©΄
print(0) # 0 μΆλ ₯
sys.exit() # μ€νμ€μΈ μ€ν¬λ¦½νΈ μ’
λ£
for j in range(n):
for i in range(m):
if storage[j][i] == 1: # μ΅μ ν λ§ν λΌλ©΄ (1)
q.append((i, j)) # μ΅μ ν λ§ν μ μ’ν queueμ μΆκ°
while q: # qμ μμκ° μλ κ²½μ° κ³μ λ°λ³΅
x, y = q.popleft() # q μμ κΊΌλ΄μ x, yμ ν λΉ
for k in range(4):
nx = dx[k] + x
ny = dy[k] + y
if 0 <= nx < m and 0 <= ny < n and storage[ny][nx] == 0: # λ²μ λ΄μ μμΌλ©΄μ, μ μ΅μ ν λ§ν μΌ κ²½μ° (0)
storage[ny][nx] = 1 # μ΅μ ν λ§ν λ‘ λ³κ²½
q.append((nx, ny)) # ν΄λΉ μ’ν queueμ μΆκ°
dis[ny][nx] = dis[y][x] + 1 # ν λ§ν κ° μ΅μ λ μ§ λ£κΈ°
ans = 0 # λ μ§λ₯Ό λ΄μ ans ν λΉ
for c2 in storage: # storage κ° νλ§λ€ νμ
if 0 in c2: # μ μ΅μ ν λ§ν κ° μμ§ μλ€λ©΄
print(-1) # -1 μΆλ ₯
sys.exit(0) # μ€ν¬λ¦½νΈ μ€ν μ’
λ£
for l1 in range(n):
for l2 in range(m):
if dis[l1][l2] > ans:
ans = dis[l1][l2] # μ΅λκ° ν λΉ
print(ans) # ans μΆλ ₯
'𧩠Algorithm > π¨ Python' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[νμ΄μ¬] λ°±μ€ 1436λ² λ¬Έμ : μνκ°λ μ (2) | 2022.08.27 |
---|---|
[νμ΄μ¬] λ°±μ€ 1926λ² λ¬Έμ : κ·Έλ¦Ό (0) | 2022.08.27 |
[νμ΄μ¬] λ°±μ€ 1874λ² λ¬Έμ : μ€ν μμ΄ (0) | 2022.08.27 |
[νμ΄μ¬] λ°±μ€ 3135λ² λ¬Έμ : λΌλμ€ (0) | 2022.08.26 |
[νμ΄μ¬] λ°±μ€ 2468λ² λ¬Έμ : μμ μμ (0) | 2022.08.26 |