BOJ 2178: λ―Έλ‘ νμ (Python)
λ¬Έμ
https://www.acmicpc.net/problem/2178
2178λ²: λ―Έλ‘ νμ
첫째 μ€μ λ μ μ N, M(2 ≤ N, M ≤ 100)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ Mκ°μ μ μλ‘ λ―Έλ‘κ° μ£Όμ΄μ§λ€. κ°κ°μ μλ€μ λΆμ΄μ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
www.acmicpc.net
μ½λ
import sys
from collections import deque
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or nx>=n or ny<0 or ny>=m:
continue
if graph[nx][ny] == 0:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx,ny))
return graph[n-1][m-1]
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
print(bfs(0,0))
νμ΄
bfsλ₯Ό μ΄μ©ν΄ λ¬Έμ λ₯Ό νμλ€. (0,0) μμΉλΆν° νμμ μμνμ¬ μνμ’μ°μ μλ κ°μ΄ 1μ΄λΌλ©΄, μ¦ μμ§ μ§λκ°μ§ μμκ³ μ§λκ° μ μλ κΈΈμ΄λΌλ©΄ κ·Έ κ°μ μ΄λκΉμ§ μ¨ κ²½λ‘μ + 1 μ ν κ°μ λ£λλ€. κ·Έλ¦¬κ³ κ·Έκ²μ μ’ν κ°μ νμ λ΄λλ€.
νμ λ¨λκ² μμ λκΉμ§ λ°λ³΅νκ³ λλ©΄ graph[n-1][m-1] ( (0,0)λΆν° μμνμΌλ―λ‘ μ€λ₯Έμͺ½ κ°μ₯ μλμ μ’νλ (n-1, m-1)μ΄λ€. )μ λ€μ΄κ° μλ κ°μ΄ μ΅μ κ²½λ‘ κ°μΌλ‘ μ λ΅μ΄λ€.