๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
[๊ฐ๋จํ BFS] ๋ฏธ๋ก ๊ฒ์ ๋ณธ๋ฌธ
728x90
๋ฐ์ํ
์ฐธ๊ณ ํ์ต๋๋ค. ๊ฐ์ฌํฉ๋๋ค
https://doyyy.tistory.com/144
๋ฏธ๋ก๊ฒ์
๋๋น์ด๋ N X M ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ ํํ์ ๋ฏธ๋ก์ ๊ฐํ๋ค
๋ฏธ๋ก์๋ ์ฌ๋ฌ ๋ง๋ฆฌ์ ๊ดด๋ฌผ์ด ์์ด ์ด๋ฅผ ํผํด ํ์ถํด์ผ ํ๋ค
๋๋น์ด์ ์์น๋ (1,1)์ด๋ฉฐ ๋ฏธ๋ก์ ์ถ๊ตฌ๋ (N,M)์ ์์น์ ์กด์ฌํ๋ฉฐ ํ ๋ฒ์ ํ ์นธ์ฉ ์ด๋
์ด ๋ ๊ดด๋ฌผ์ด ์๋ ๋ถ๋ถ์ 0์ผ๋ก, ๊ดด๋ฌผ์ด ์๋ ๋ถ๋ถ์ 1๋ก ํ์
๋ฏธ๋ก๋ ๋ฐ๋์ ํ์ถํ ์ ์๋ ํํ๋ก ์ ์
์ด๋ ๋๋น์ด๊ฐ ํ์ถํ๊ธฐ ์ํด ์์ง์ฌ์ผ ํ๋ ์ต์ ์นธ์ ๊ฐ์
์นธ์ ์ ๋๋ ์์ ์นธ๊ณผ ๋ง์ง๋ง ์นธ์ ๋ชจ๋ ํฌํจํด์ ๊ณ์ฐ
from collections import deque
# N X M ๋ฏธ๋ก
n, m = map(int, input().split())
# ๋ฏธ๋ก์ ์ ๋ณด
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
# ๋ฐฉํฅ ๋ฒกํฐ
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque()
queue.append([x, y])
while queue:
# ๊ฐ ์ด๊ธฐํ
x, y = queue.popleft()
# 4๊ฐ์ง ๋ฐฉํฅ
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# ๋ฒ์ ๋ฒ์ด๋ ๊ฒฝ์ฐ ๋ฌด์
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
# ๊ดด๋ฌผ ์๋ ๊ฒฝ์ฐ ๋ฌด์
if graph[nx][ny] == 0:
continue
# ๊ดด๋ฌผ์ด ์๋ ๋ถ๋ถ์ด๋ค!
# ํ์ฌ ์์น์์ ์ด๋!
if graph[nx][ny] == 1:
queue.append([nx,ny])
graph[nx][ny] = graph[x][y] + 1
bfs(0,0)
print(graph[n-1][m-1])
728x90
๋ฐ์ํ
'๐ฆฅ ์ฝํ ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๊ฐ๋จํ DFS] ์ผ์ ๋ฌธ์ (0) | 2023.04.12 |
---|---|
[LG ์ฝ๋ฉํ ์คํธ ์์ ] ๋ง๋ฆฌ์ค ๊ฒ์ (0) | 2023.04.12 |
[๋ด๊ฐ ๋ณผ ์ ์ฉํ ๋ชจ์] ์ฝ๋ฉ ํ ์คํธ (0) | 2022.10.07 |
Comments