16. 게임 맵 최단거리 ★ (BFS, zip)

유형 : BFS

풀이 시간 : 30분

 

*최단거리 == BFS를 이용해 풀이하자!!*

*visted queue를 잊지 말자!!*

from collections import deque 

def solution(maps):
    answer = 0
    msize = len(maps)
    nsize = len(maps[0])
    queue = deque()
    visited = deque()
    
    #initialization
    queue.append([0, 0])
    visited.append([0, 0])
    #순회를 위한 dx, dy
    dx = [1, 0, 0, -1]
    dy = [0, 1, -1, 0]
    
    #bfs search
    while queue:
        [currx, curry] = queue.popleft()
        for x, y in zip(dx, dy):
            if currx + x < msize and currx + x >= 0 and curry + y < nsize and curry + y >= 0: 
                if maps[currx+x][curry+y] != 0 and [currx+x, curry+y] not in visited:
                    queue.append([currx+x, curry+y])
                    visited.append([currx+x, curry+y])
                    maps[currx+x][curry+y] += maps[currx][curry]

    if maps[msize-1][nsize-1] == 1:
        return -1
    else:
        return maps[msize-1][nsize-1]

 

시간 초과가 발생해서 최적화를 좀 해 보자. 

visited를 queue로 만드는 것이 아니라 true, false 배열로 만들어 보자. 

 

from collections import deque 

def solution(maps):
    answer = 0
    msize = len(maps)
    nsize = len(maps[0])
    queue = deque()
    visited = [[False for i in range(nsize)] for j in range(msize)]
    
    #initialization
    queue.append([0, 0])
    visited[0][0] = True
    
    #순회를 위한 dx, dy
    dx = [1, 0, 0, -1]
    dy = [0, 1, -1, 0]
    
    #bfs search
    while queue:
        [currx, curry] = queue.popleft()
        for x, y in zip(dx, dy):
            if currx + x < msize and currx + x >= 0 and curry + y < nsize and curry + y >= 0: 
                if maps[currx+x][curry+y] != 0 and visited[currx+x][curry+y] == False:
                    queue.append([currx+x, curry+y])
                    visited[currx+x][curry+y] = True
                    maps[currx+x][curry+y] += maps[currx][curry]

    if maps[msize-1][nsize-1] == 1:
        return -1
    else:
        return maps[msize-1][nsize-1]

 

시간 초과 없이 해결되었다. 

 

<참고한 >