BFS-최단경로찾기

BFS-최단경로찾기 예제코드

from collections import deque

def solution(maze,r,c):
    answer=0
    maze_r_len=len(maze)
    maze_c_len=len(maze[0])
    visited=[[0]*maze_c_len for _ in range(maze_r_len)]
    count_map=[[0]*maze_c_len for _ in range(maze_r_len)]
    dr=[-1,0,1,0]
    dc=[0,-1,0,1]
    print(visited)

    q=deque()
    q.append([r,c])
    count=0

    #방법1
    # while(q):
    #     current_r,current_c=q.popleft()
    #     visited[current_r][current_c]=1
    #     if maze[current_r][current_c]=="e":
    #         answer=count_map[current_r][current_c]
    #         break
        
    #     for i in range(4):
    #         next_r=current_r+dr[i]
    #         next_c=current_c+dc[i]
    #         if 0<=next_r<maze_r_len and 0<=next_c<maze_c_len and maze[next_r][next_c]!=1 and visited[next_r][next_c]!=1:#이동가능할때
    #             q.append([next_r,next_c])
    #             count_map[next_r][next_c]=count_map[current_r][current_c]+1 #가장중요한부분

    # print(count_map)

    #방법2
    visited[r][c]=1 #현재위치 방문입력.

    while(q):
        current_r,current_c=q.popleft()
        # visited[current_r][current_c]=1
        if maze[current_r][current_c]=="e":
            answer=visited[current_r][current_c]
            break
        
        for i in range(4):
            next_r=current_r+dr[i]
            next_c=current_c+dc[i]
            if 0<=next_r<maze_r_len and 0<=next_c<maze_c_len and maze[next_r][next_c]!=1 and visited[next_r][next_c]==0:#이동가능할때
                q.append([next_r,next_c])
                visited[next_r][next_c]=visited[current_r][current_c]+1 #가장중요한부분

    print(visited)

    return answer



print(solution([[0,0,1,0],[1,0,0,0],[0,1,0,0],["e",0,0,0]],1,2))

#0010
#10c0  c가 현재위치.
#0100
#e000  e가 목표위치. maze[r][c]==e 까지가는 최단 이동거리 구하기. ==4

#3202
#0101
#0012
#4323