백준 2178 미로 탐색 Python 3

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2178.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque

def BFS(sx, sy, miro, N, M):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    visit = [[0]*(M+1) for _ in range(N+1)]
    visit[sy][sx] = 1
    q = deque([[sx, sy, 1]])
    while q:
        x, y, cnt = q.popleft()
        if y == N and x == M:
            print(cnt)
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <= M and 0 <= ny <= N:
                if not visit[ny][nx] and miro[ny][nx]:
                    visit[ny][nx] = 1
                    q.append([nx, ny, cnt+1])


input = sys.stdin.readline
N, M = map(int, input().split())
miro = list()
for _ in range(N):
    miro.append(list(map(int, input().strip())))
BFS(0, 0, miro, N-1, M-1)

---

풀이 과정

풀이 시간 15분

import sys
from collections import deque

def BFS(sx, sy, miro, N, M):
	#좌, 상, 우, 하
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    
    visit = [[0]*(M+1) for _ in range(N+1)]
    visit[sy][sx] = 1
    q = deque([[sx, sy, 1]])
    
    while q:
        x, y, cnt = q.popleft()
        
        #목적지에 도착한 경우,
        if y == N and x == M:
            print(cnt)
            return
            
        #인접한 4 방향 탐색    
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #미로 밖을 벗어나지 않으면서 (nx, ny)가 이동할 수 있는 칸인 경우,
            if 0 <= nx <= M and 0 <= ny <= N:
                if not visit[ny][nx] and miro[ny][nx]:
                    visit[ny][nx] = 1
                    q.append([nx, ny, cnt+1])


input = sys.stdin.readline
N, M = map(int, input().split())
miro = list()
for _ in range(N):
    miro.append(list(map(int, input().strip())))
BFS(0, 0, miro, N-1, M-1)

#시간복잡도 = O(N*M), 공간복잡도 = O(N*M)