프로그래머스 게임 맵 최단거리 파이썬

1. dfs 사용 (x)

bfs 사용하기 위해서는 현재 위치를 다시 방문하지 않아야 하는데 이 문제는 오른쪽, 아래로 이동할 뿐만 아니라 위, 왼쪽으로 이동도 가능하므로 현재 위치를 또 방문할 가능성이 생긴다. 따라서 bfs가 아닌 완전탐색 문제로 풀어야 한다. 그러나 완전탐색으로 풀면 깊이가 너무 깊어져 효율성 테스트에서 런타임 오류가 발생한다. 

 

import sys
answer= sys.maxsize #int 최대값으로 초기화
# cnt = 이동한 칸 횟수 , point = 현재 위치 좌표 , check = 방문한 좌표인지 확인하기 위해
def dfs(maps,cnt,point,check): 
    global answer
    if point[0]==len(maps)-1 and point[1]==len(maps[0])-1: #도착지점 좌표
        answer=min(answer,cnt)  #min함수 사용하며 answer update
    elif (point[0]>=0 and point[1]>=0) and (point[0]<len(maps) and point[1]<len(maps[0])):  #point 값이 지도 좌표 범위 내에 좌표값인지 확인
        if maps[point[0]][point[1]]!=0:
            if check[point[0]][point[1]]==False:  #현재 위치가 방문되지 않은 위치여야 함
                check[point[0]][point[1]]=True  #현재 위치를 방문된 위치로 변경(무한 재귀 방지)
                dfs(maps,cnt+1,[point[0]+1,point[1]],check) #아래로 이동
                dfs(maps,cnt+1,[point[0],point[1]+1],check) #오른쪽 이동
                dfs(maps,cnt+1,[point[0]-1,point[1]],check) #위로 이동
                dfs(maps,cnt+1,[point[0],point[1]-1],check) #왼쪽 이동
                check[point[0]][point[1]]=False 

def solution(maps):
    global answer
    check=[[False for i in maps[0]] for i in maps]  #현재 지도 맵 배열 크기로 초기화
    dfs(maps,1,[0,0],check)
    if answer==sys.maxsize:
        return -1
    else:
        return answer'

 

 

1. bfs 사용

방문하고자 하는 map의 위치를 저장하는 리스트를 만들었다. 현재 위치가 방문된 적이 없고 지도좌표범위 내에 있다면 현재 위치를 방문한 좌표로 만들고(check배열 이용) 이동한 칸 횟수를 1 늘린다(cnt이용). 현재 위치가 도착 위치라면 이동한 칸 횟수를 반환하고 도착 위치가 아닐 경우 현재 위치에서 갈수 있는 위치들을 리스트에 추가해준다. 큐를 이용할 경우 추가,삭제시 O(n)의 시간 복잡도를 가지기 때문에 리스트로 구현하여 탐색한 노드를 제외하고 추가한 노드들만 방문할 수 있도록 for문에 시작 위치를 계속 변경하여 주었다.

 

def solution(maps):
    answer=0
    check=[[False for i in maps[0]] for i in maps]  #현재 지도 맵 배열 크기로 초기화
    que=[[0,0,0]]
    cnt,p=0,0
    while(True):
        tmp=len(que) #밑에 for문에서 현재 que에 저장된 값까지 돌기 때문에 그 뒤부터 for문 돌 수 있도록 현재 que의 길이를 저장
        if p==len(que):
                return -1
        for i in range(p,len(que)):
            x=que[i][0] #x좌표
            y=que[i][1] #y좌표
            if (x>=0 and y>=0) and (x<len(maps) and y<len(maps[0])):
                if maps[x][y]!=0 and not check[x][y]:
                    check[x][y]=True
                    answer+=1
                    cnt=que[i][2]+1
                    if x==len(maps)-1 and y==len(maps[0])-1:
                        return cnt
                    que.append([x+1,y,cnt])
                    que.append([x,y+1,cnt])
                    que.append([x-1,y,cnt])
                    que.append([x,y-1,cnt])
        p=tmp  #다음 for문에서 새로 저장된 que의 값들만 돌 수 있도록 p 변경
    
    return answer