Level 2 게임 맵 최단거리 Python 3

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_게임맵최단거리.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import deque
answer = -1

def bfs(maps):
    global answer
    visit = [[0]*len(maps[0]) for _ in range(len(maps))]
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    q = deque()
    q.append([0, 0, 1])
    visit[0][0] = 1
    while q:
        x, y, cnt = q.popleft()
        if x == len(maps[0])-1 and y == len(maps)-1:
            answer = cnt
            return
        for ddx, ddy in zip(dx, dy):
            nx = x + ddx
            ny = y + ddy
            if 0 <= nx < len(maps[0]) and 0 <= ny < len(maps):
                if not maps[ny][nx]: continue
                if visit[ny][nx]: continue
                visit[ny][nx] = 1
                q.append([nx, ny, cnt+1])
                
    
def solution(maps):
    bfs(maps)
    return answer

---

풀이 과정

풀이 시간 11분

from collections import deque
answer = -1

def bfs(maps):
    global answer
    #방문 처리
    visit = [[0]*len(maps[0]) for _ in range(len(maps))]
    #좌 상 우 하
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    
    q = deque()
    #[시작 x좌표, 시작 y좌표, 칸 수] 큐에 넣기
    q.append([0, 0, 1])
    #시작 칸 방문 처리
    visit[0][0] = 1
    
    while q:
        x, y, cnt = q.popleft()
        
        #상대 팀 진영에 도착한 경우, answer 값 갱신하고 탐색을 종료한다
        if x == len(maps[0])-1 and y == len(maps)-1:
            answer = cnt
            return
            
        #인접한 4방향 탐색하기
        for ddx, ddy in zip(dx, dy):
            nx = x + ddx
            ny = y + ddy
            
            #경로 내에 위치하는 경우,
            if 0 <= nx < len(maps[0]) and 0 <= ny < len(maps):
            	#벽이 있는 칸이라면, 무시한다
                if not maps[ny][nx]: continue
                #이전에 방문한 칸이라면, 무시한다
                if visit[ny][nx]: continue
                
                #해당 칸 방문
                visit[ny][nx] = 1
                q.append([nx, ny, cnt+1])
                
    
def solution(maps):
    bfs(maps)
    return answer

#시간복잡도 = O(V+E), 공간복잡도 = O(V)