027 미로 탐색

첫번째 코드

 

어...DFS보다는 익숙하지 않아도 재귀가 덜 들어가서 할 수 있겠...

네? 행렬이요?! 도와줘요 책님;;;

상하좌우를 살피면서  방문 리스트도 행렬로 만들어 확인하면 된다...

어... 문제를 이해하고 코드를 확인하면 이해가 된다...

근데 과연 나 혼자서 할 수 있을까...?

 

import sys
input = sys.stdin.readline
from collections import deque

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

n, m = map(int, input().split())
A = [[0] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]

for i in range(n):
    numbers = list(input())
    for j in range(m):
        A[i][j] = int(numbers[j])

def BFS(i, j):
    queue = deque()
    queue.append((i, j))
    visited[i][j] = True
    
    while queue:
        now = queue.popleft()
        for k in range(4):
            x = now[0] + dx[k]
            y = now[1] + dy[k]
            if x>=0 and y>=0 and x<n and y<m:
                if A[x][y] != 0 and not visited[x][y]:
                    visited[x][y] = True
                    A[x][y] = A[now[0]][now[1]] + 1
                    queue.append((x, y))

BFS(0, 0)
print(A[n-1][m-1])            

 

통과:(

혼자 할 수 있는 날이 오겠지!!

아무래도 행렬로 표현해서 DFS, BFS를 적용하는 것은 처음해보는 일이라서 킁;

BFS, DFS 문제 모음을 한번 풀어볼 필요성이 있댜.... 그래도 알았잖아 BFS의 존재를 음음!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/2178.%E2%80%85%EB%AF%B8%EB%A1%9C%E2%80%85%ED%83%90%EC%83%89

programmers/백준/Silver/2178. 미로 탐색 at main · ornni/programmers