(python)프로그래머스-게임 맵 최단거리

게임 맵 최단거리

문제

---

제한사항

---

풀이

첫번째 풀이-> 시간초과

BFS를 사용해서 금방 풀었지만 효율성 테스트가 다 틀려서 처음엔 문제를 틀렸다.
시간초과가 난 부분을 찾아야 했다.
알고보니 visited부분에서 시간초과가 났다. 밑에 코드와 같이 방문한 노드를 찾게 되면 visited에 들어있는 노드들을 모두 방문하면서 확인해야하므로 시간 초과가 난다.
이부분을 visited를 이차원 배열로 바꾼 후 확인하는 코드로 수정해 주었다.

from collections import deque
answer=-1
def BFS(x,y,current_sum,maps):
    global answer
    n=len(maps)
    m=len(maps[0])
    q=deque()
    q.append((x,y,current_sum))
    #동서남북
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    visited=[]
    while q:
        x,y,current_sum=q.popleft()
        if x==n-1 and y==m-1:
            answer=current_sum
            break
        else:
            for i in range(4):
                nx=x+dx[i]
                ny=y+dy[i]
                if nx<0 or ny<0 or nx>=n or ny>=m or maps[nx][ny]==0:
                    continue
                else:
                    if (nx,ny) not in visited:
                        visited.append((nx,ny))
                        q.append((nx,ny,current_sum+1))
def solution(maps):
    global answer
    BFS(0,0,1,maps)
    return answer

---

두번째 풀이->정답

from collections import deque
answer=-1
def BFS(x,y,current_sum,maps):
    global answer
    n=len(maps)
    m=len(maps[0])
    q=deque()
    q.append((x,y,current_sum))
    #동서남북
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    visited=[[False]*m for i in range(n)]
    while q:
        x,y,current_sum=q.popleft()
        if x==n-1 and y==m-1:
            answer=current_sum
            break
        else:
            for i in range(4):
                nx=x+dx[i]
                ny=y+dy[i]
                if nx<0 or ny<0 or nx>=n or ny>=m or maps[nx][ny]==0:
                    continue
                else:
                    if visited[nx][ny]==False:
                        visited[nx][ny]=True
                        q.append((nx,ny,current_sum+1))
def solution(maps):
    global answer
    BFS(0,0,1,maps)
    return answer