[CodingStudy] BFS-게임맵 최단거리

틀린 부분이 있다면 언제든지 댓글 남겨주세요! 

---

프로그래머스-BFS_게임맵 최단거리

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

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

---

생각해야 할 부분

 

 1. BFS(Breadth First Search) 알고리즘 개념 이용 > 한번 방문한 위치 재방문하지 않도록 이미 지나온 길은 0으로 visit 체크

 2. collection 모듈에서 제공하는 deque는 stack(list)과 달리 list의 앞뒤로 값을 변경할 수 있으며 시간복잡도가 list에 비해 짧기 때문에 효율성을 높이는데 유용

3. x, y 헷갈림 주의!!!

4. 방문처리를 큐에 넣을때 해야 다른 경로에서 이 칸을 중복으로 큐에 넣는 경우를 방지할 수 있음,

    큐에서 꺼낼 때 하게 되면 중복으로 큐에 넣는 경우가 생길 수 있음!!!

5. 가장 최단거리에 먼저 도착해서 return 되므로 더 긴 경우는 생각하지 않아도 됨

from collections import deque

def bfs(maps, que):
    # direct=완료지점에 더 가까운 곳 부터 확인하도록 순서를 지정함
    direct=[[1,0],[0,1],[-1,0],[0,-1]]  # x, y
    while que:
        q=que.popleft()      # 더 가까운 곳 부터 해야 최단거리
        if (len(maps[0])-1)==q[1] and (len(maps)-1)==q[0]:
            return q[2]       # 가장 최단거리 리턴
        for dic in direct:    # 각 방향 별로
            ax=q[0]+dic[0]    # x
            ay=q[1]+dic[1]    # y
            if len(maps)>ax>-1 and len(maps[0])>ay>-1 and maps[ax][ay]==1:
                maps[ax][ay]=0   # 지난 곳 다시 지나지 않도록 방문처리
                que.append([ax, ay, q[2]+1])    
    return -1   # que를 다 돌아도 끝까지 도달하지 못하는 경우
            
def solution(maps):
    que=deque([(0,0,1)])    # (x, y, visit count)
    return bfs(maps, que)