[Python] λ°±μ€ 2178 λ―Έλ‘ νμ (BFS)


π λ¬Έμ
N×Mν¬κΈ°μ λ°°μ΄λ‘ ννλλ λ―Έλ‘κ° μλ€.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
λ―Έλ‘μμ 1μ μ΄λν μ μλ μΉΈμ λνλ΄κ³ , 0μ μ΄λν μ μλ μΉΈμ λνλΈλ€. μ΄λ¬ν λ―Έλ‘κ° μ£Όμ΄μ‘μ λ, (1, 1)μμ μΆλ°νμ¬ (N, M)μ μμΉλ‘ μ΄λν λ μ§λμΌ νλ μ΅μμ μΉΈ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. ν μΉΈμμ λ€λ₯Έ μΉΈμΌλ‘ μ΄λν λ, μλ‘ μΈμ ν μΉΈμΌλ‘λ§ μ΄λν μ μλ€.
μμ μμμλ 15μΉΈμ μ§λμΌ (N, M)μ μμΉλ‘ μ΄λν μ μλ€. μΉΈμ μ λμλ μμ μμΉμ λμ°© μμΉλ ν¬ν¨νλ€.
μ λ ₯
첫째 μ€μ λ μ μ N, M(2 ≤ N, M ≤ 100)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ Mκ°μ μ μλ‘ λ―Έλ‘κ° μ£Όμ΄μ§λ€. κ°κ°μ μλ€μ λΆμ΄μ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
μΆλ ₯
첫째 μ€μ μ§λμΌ νλ μ΅μμ μΉΈ μλ₯Ό μΆλ ₯νλ€. νμ λμ°©μμΉλ‘ μ΄λν μ μλ κ²½μ°λ§ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
μμ μ λ ₯ 1
4 6
101111
101010
101011
111011
μμ μΆλ ₯ 1
15
μμ μ λ ₯ 2
4 6
110110
110110
111111
111101
μμ μΆλ ₯ 2
9
μμ μ λ ₯ 3
2 25
1011101110111011101110111
1110111011101110111011101
μμ μΆλ ₯ 3
38
μμ μ λ ₯ 4
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
μμ μΆλ ₯ 4
13
π νμ΄
π¬ Code
import sys
from collections import deque
input = sys.stdin.readline
def bfs(x, y):
q = deque([(x-1, y-1)])
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
q.append((nx, ny))
maze[nx][ny] += maze[x][y]
return maze[n-1][m-1]
if __name__ == '__main__':
n, m = map(int, input().split())
maze = []
for _ in range(n):
maze.append(list(map(int, input().rstrip())))
# λ°©ν₯λ²‘ν° (μ, ν, μ’, μ°)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
print(bfs(1, 1))
π‘ Solution
μ΄μ½ν μμ μμ λ‘ λμλ λ¬Έμ λΌ μ½κ² νμ μμμ΅λλ€.
- μ’νκ° μ£Όμ΄μ§λ©΄ ν΄λΉ μ’νμ μνμ’μ° μ’νλ‘ μ΄λν μ μλμ§ κ°κ° 체ν¬νκΈ° μν΄ μ’νλ§λ€ forλ¬Έμ 4λ² λ립λλ€.
- nx, nyλ μ΄λμ’νλ₯Ό λνλΈλ€. μ΄λμ’νκ° (-1, -1)μ²λΌ μ’νλ₯Ό λ²μ΄λμ§ μμκ³ ν΄λΉ μ’νμ λμΈ κ°μ΄ 1μ΄λΌλ©΄ κ·Έ κ³³μΌλ‘ μ΄λν μ μλ κ²μ΄λ―λ‘ μ΄λ ν νμ (nx, ny)μμ λ£μ΄μ€λλ€.
- μ§λμΌ νλ μ΅μ μΉΈμλ₯Ό ꡬν΄μΌ νλ―λ‘ μ΄λν λλ§λ€ μ΄λμΉΈμλ₯Ό λμ μν΅λλ€. maze[x][y]μμ maze[nx][ny]λ‘μ μ΄λμΉΈμλ 1μΉΈμΈλ°, maze[nx][ny]μ κ°μ΄ μ΄λ―Έ 1μ΄κΈ° λλ¬Έμ maze[nx][ny] += maze[x][y] ν΄μ£Όλ©΄ maze[nx][ny]μ μ¬νκΉμ§ μ§λμ¨ μΉΈμκ° μ λ ₯λ©λλ€.
- λͺ©ν μ’νμ κ°μ μΆλ ₯ν΄μ£Όλ©΄ λ!