-
[Python] λ°±μ€ - 7569 ν λ§ν__Python/__Algorithm 2022. 2. 12. 12:41
λ¬Έμ
https://www.acmicpc.net/problem/7569
πΉ λ¬Έμ
μ² μμ ν λ§ν λμ₯μμλ ν λ§ν λ₯Ό 보κ΄νλ ν° μ°½κ³ λ₯Ό κ°μ§κ³ μλ€. ν λ§ν λ μλμ κ·Έλ¦Όκ³Ό κ°μ΄ 격μλͺ¨μ μμμ μΉΈμ νλμ© λ£μ λ€μ, μμλ€μ μμ§μΌλ‘ μμ μ¬λ €μ μ°½κ³ μ 보κ΄νλ€.
μ°½κ³ μ 보κ΄λλ ν λ§ν λ€ μ€μλ μ μ΅μ κ²λ μμ§λ§, μμ§ μ΅μ§ μμ ν λ§ν λ€λ μμ μ μλ€. λ³΄κ΄ ν νλ£¨κ° μ§λλ©΄, μ΅μ ν λ§ν λ€μ μΈμ ν κ³³μ μλ μ΅μ§ μμ ν λ§ν λ€μ μ΅μ ν λ§ν μ μν₯μ λ°μ μ΅κ² λλ€. νλμ ν λ§ν μ μΈμ ν κ³³μ μ, μλ, μΌμͺ½, μ€λ₯Έμͺ½, μ, λ€ μ¬μ― λ°©ν₯μ μλ ν λ§ν λ₯Ό μλ―Ένλ€. λκ°μ λ°©ν₯μ μλ ν λ§ν λ€μκ²λ μν₯μ μ£Όμ§ λͺ»νλ©°, ν λ§ν κ° νΌμ μ μ λ‘ μ΅λ κ²½μ°λ μλ€κ³ κ°μ νλ€. μ² μλ μ°½κ³ μ 보κ΄λ ν λ§ν λ€μ΄ λ©°μΉ μ΄ μ§λλ©΄ λ€ μ΅κ² λλμ§ κ·Έ μ΅μ μΌμλ₯Ό μκ³ μΆμ΄ νλ€.
ν λ§ν λ₯Ό μ°½κ³ μ 보κ΄νλ 격μλͺ¨μμ μμλ€μ ν¬κΈ°μ μ΅μ ν λ§ν λ€κ³Ό μ΅μ§ μμ ν λ§ν λ€μ μ λ³΄κ° μ£Όμ΄μ‘μ λ, λ©°μΉ μ΄ μ§λλ©΄ ν λ§ν λ€μ΄ λͺ¨λ μ΅λμ§, κ·Έ μ΅μ μΌμλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νλΌ. λ¨, μμμ μΌλΆ μΉΈμλ ν λ§ν κ° λ€μ΄μμ§ μμ μλ μλ€.
πΉ μ λ ₯
첫 μ€μλ μμμ ν¬κΈ°λ₯Ό λνλ΄λ λ μ μ M,Nκ³Ό μμμ¬λ €μ§λ μμμ μλ₯Ό λνλ΄λ Hκ° μ£Όμ΄μ§λ€. Mμ μμμ κ°λ‘ μΉΈμ μ, Nμ μμμ μΈλ‘ μΉΈμ μλ₯Ό λνλΈλ€. λ¨, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 μ΄λ€. λμ§Έ μ€λΆν°λ κ°μ₯ λ°μ μμλΆν° κ°μ₯ μμ μμκΉμ§μ μ μ₯λ ν λ§ν λ€μ μ λ³΄κ° μ£Όμ΄μ§λ€. μ¦, λμ§Έ μ€λΆν° Nκ°μ μ€μλ νλμ μμμ λ΄κΈ΄ ν λ§ν μ μ λ³΄κ° μ£Όμ΄μ§λ€. κ° μ€μλ μμ κ°λ‘μ€μ λ€μ΄μλ ν λ§ν λ€μ μνκ° Mκ°μ μ μλ‘ μ£Όμ΄μ§λ€. μ μ 1μ μ΅μ ν λ§ν , μ μ 0 μ μ΅μ§ μμ ν λ§ν , μ μ -1μ ν λ§ν κ° λ€μ΄μμ§ μμ μΉΈμ λνλΈλ€. μ΄λ¬ν Nκ°μ μ€μ΄ Hλ² λ°λ³΅νμ¬ μ£Όμ΄μ§λ€.
ν λ§ν κ° νλ μ΄μ μλ κ²½μ°λ§ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
πΉ μΆλ ₯
μ¬λ¬λΆμ ν λ§ν κ° λͺ¨λ μ΅μ λκΉμ§ μ΅μ λ©°μΉ μ΄ κ±Έλ¦¬λμ§λ₯Ό κ³μ°ν΄μ μΆλ ₯ν΄μΌ νλ€. λ§μ½, μ μ₯λ λλΆν° λͺ¨λ ν λ§ν κ° μ΅μ΄μλ μνμ΄λ©΄ 0μ μΆλ ₯ν΄μΌ νκ³ , ν λ§ν κ° λͺ¨λ μ΅μ§λ λͺ»νλ μν©μ΄λ©΄ -1μ μΆλ ₯ν΄μΌ νλ€.
νμ΄ λ°©λ²
πΉ κ·Έλν νμ
πΉ BFS (λλΉμ°μ νμ)
- λͺ¨λ μ΅μ ν λ§ν μ΄κ±°λ(1), ν λ§ν κ° νλλ μλ κ²½μ°(-1)μλ exit()μ ν΅ν΄ λ°λ‘ νλ‘κ·Έλ¨ μ’ λ£
- μμ΅μ ν λ§ν (0)λ chkλ₯Ό ν΅ν΄ count+1, BFSλ‘ λ°©λ¬Έμ count-1
- μΈμ ν ν λ§ν κ° μ΅μ§ μμλ€λ©΄, νμ¬ ν λ§ν μΌμμμ 1μΌ μΆκ°, qμ λ£μ΄ λ°©λ¬Έ μ²λ¦¬
- BFS μ’ λ£ ν μ¬μ ν chkκ° 0μ΄ μλλΌλ©΄, μμ΅μ ν λ§ν (0)κ° μ‘΄μ¬ > μΆλ ₯ : -1
- BFS μ’ λ£ ν λͺ¨λ ν λ§ν κ° μ΅μλ€λ©΄ > μΆλ ₯ : λ§μ§λ§μ μ΅μ ν λ§ν μ μΌμ -1
πΉ νλ Έμ΅λλ€ ν΄κ²° > κ²μν λ°λ‘λ€ μ°Έκ³ (3μ°¨μ μΈλ±μ€ μ κ·Ό μλ¬ -- λ²μ μλͺ» μ§μ )
λ°λ‘ π½
λ보기
3 3 1
1 1 0
0 0 0
0 0 0μ λ΅ > 3 5 3 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1μ λ΅ > 0 2 2 6
0 0
0 0
0 0
0 0
0 1
0 0
0 0
0 0
0 0
0 0
0 0
0 0μ λ΅ > 5 μ€ν¨
μ²μ μΆλ ₯: -1ꡬν μ½λ
import sys from collections import deque def bfs(queue,chk): while q: f,x,y = q.popleft() df = [0,0,0,0,1,-1] dx = [-1,1,0,0,0,0] dy = [0,0,-1,1,0,0] for k in range(6): nf = f + df[k]; nx = x + dx[k]; ny = y + dy[k] if 0<=nf<h and 0<=nx<m and 0<=ny<n and box[nf][nx][ny]==0: box[nf][nx][ny] = box[f][x][y] +1 q.append([nf,nx,ny]) chk-=1 if chk != 0: return -1 return box[f][x][y]-1 n,m,h = map(int, sys.stdin.readline().split()) box = [[list(map(int, sys.stdin.readline().split())) for _ in range(m)] for _ in range(h)] q = deque([]) chk = 0 for f in range(h): for i in range(m): for j in range(n): if box[f][i][j] == 1: q.append([f,i,j]) elif box[f][i][j] == 0: chk += 1 if chk == 0: print(0) exit(0) print(bfs(q,chk))
μ€ν κ²°κ³Ό
π‘
πΉ exit(0)μ ν΅ν΄ λ°λ‘ νλ‘κ·Έλ¨μ μ μ μ’ λ£μν¬ μ μλ€.
https://www.delftstack.com/ko/howto/python/python-exit-program/
728x90'__Python > __Algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Python] λ°±μ€ - 1913 λ¬ν½μ΄(κΈ°μ΄ λ°°μ΄λ€λ£¨κΈ°) (0) 2022.03.24 [Python] λ°±μ€ - 2468 μμ μμ (0) 2022.02.22 [Python] λ°±μ€ - 1439 λ€μ§κΈ° (0) 2022.01.27 [Python] λ°±μ€ - 1629 κ³±μ (0) 2022.01.13 [Python] λ°±μ€ - 1463 1λ‘λ§λ€κΈ° (0) 2022.01.07