파이썬 우선순위큐, 게임 맵 최단거리, 길찾기

프로그래머스 코딩테스트 연습

•  프로그래머스
  • 코딩테스트 연습
    • 깊이/너비 우선 탐색(DFS/BFS)
      • 게임 맵 최단거리

문제 보기

내가 푼 방식은...

• 탐색할 다음 위치들은 우선순위 큐에 저장했고,
• 위치 저장을 위한 배열을 문제에서 제공하는 maps와 같은 크기로 만들어서 inf 값을 넣어두고 탐색했는데...

from queue import PriorityQueue

def solution(maps):
    pq = PriorityQueue()

    dist = 1
    x, y = 0, 0
    sx, sy = 0, 0
    ex, ey = len(maps[0]), len(maps)
    pq.put([dist,(sx,sy)])

    INF = float("inf") #파이썬 3.5 이상에서 사용 가능
    footmap = [[INF for i in range(ex)] for j in range(ey)]

    while pq.empty() == False:
        t = pq.get()
        dist = t[0] 
        x = t[1][0]
        y = t[1][1]

        if dist < footmap[y][x] and maps[y][x] != 0 and sx <= x and x < ex and sy <= y and y < ey:
            footmap[y][x] = dist
            dist += 1
            if sx < x and maps[y][x-1] != 0:
                pq.put([dist,(x-1,y)])
            if x < ex-1 and maps[y][x+1] != 0:
                pq.put([dist,(x+1,y)])
            if sy < y and maps[y-1][x] != 0:
                pq.put([dist,(x,y-1)])
            if y < ey-1 and maps[y+1][x] != 0:
                pq.put([dist,(x,y+1)])

    if footmap[ey-1][ex-1] == INF:
        return -1
    else:
        return footmap[ey-1][ex-1]

정확성  테스트
테스트 1 〉	통과 (0.20ms, 10.3MB)
테스트 2 〉	통과 (0.15ms, 10.5MB)
테스트 3 〉	통과 (0.29ms, 10.4MB)
테스트 4 〉	통과 (0.28ms, 10.3MB)
테스트 5 〉	통과 (0.36ms, 10.4MB)
테스트 6 〉	통과 (0.27ms, 10.4MB)
테스트 7 〉	통과 (0.41ms, 10.5MB)
테스트 8 〉	통과 (0.28ms, 10.3MB)
테스트 9 〉	통과 (0.39ms, 10.3MB)
테스트 10 〉	통과 (0.36ms, 10.4MB)
테스트 11 〉	통과 (0.18ms, 10.4MB)
테스트 12 〉	통과 (0.13ms, 10.3MB)
테스트 13 〉	통과 (0.27ms, 10.4MB)
테스트 14 〉	통과 (0.21ms, 10.6MB)
테스트 15 〉	통과 (0.17ms, 10.3MB)
테스트 16 〉	통과 (0.08ms, 10.3MB)
테스트 17 〉	통과 (0.65ms, 10.5MB)
테스트 18 〉	통과 (0.10ms, 10.5MB)
테스트 19 〉	통과 (0.06ms, 10.5MB)
테스트 20 〉	통과 (0.06ms, 10.5MB)
테스트 21 〉	통과 (0.05ms, 10.5MB)
효율성  테스트
테스트 1 〉	통과 (165.44ms, 10.6MB)
테스트 2 〉	통과 (26.76ms, 10.7MB)
테스트 3 〉	통과 (68.42ms, 10.5MB)
테스트 4 〉	통과 (45.74ms, 10.5MB)

다른 사람 풀이 보니까 더 깔끔한 코드들이 많았다.

더 빠르고 효율적임.

from collections import deque

def solution(maps):
    x_move = [1, 0, -1, 0]
    y_move = [0, 1, 0, -1]

    x_h, y_h = (len(maps[0]), len(maps))
    queue = deque([(0, 0, 1)])

    while queue:
        x, y, d = queue.popleft()

        for i in range(4):
            nx = x + x_move[i]
            ny = y + y_move[i]

            if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
                if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
                    maps[ny][nx] = d + 1
                    if nx == x_h - 1 and ny == y_h - 1:
                        return d + 1

                    queue.append((nx, ny, d + 1))

    return -1

정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.3MB)
테스트 4 〉	통과 (0.04ms, 10.4MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.07ms, 10.2MB)
테스트 7 〉	통과 (0.10ms, 10.1MB)
테스트 8 〉	통과 (0.06ms, 10.1MB)
테스트 9 〉	통과 (0.05ms, 10.2MB)
테스트 10 〉	통과 (0.06ms, 10.1MB)
테스트 11 〉	통과 (0.03ms, 10.2MB)
테스트 12 〉	통과 (0.02ms, 10.1MB)
테스트 13 〉	통과 (0.06ms, 10.3MB)
테스트 14 〉	통과 (0.04ms, 10.1MB)
테스트 15 〉	통과 (0.03ms, 10.1MB)
테스트 16 〉	통과 (0.02ms, 10.2MB)
테스트 17 〉	통과 (0.07ms, 10.1MB)
테스트 18 〉	통과 (0.02ms, 10.3MB)
테스트 19 〉	통과 (0.01ms, 10.2MB)
테스트 20 〉	통과 (0.01ms, 10.2MB)
테스트 21 〉	통과 (0.01ms, 10.1MB)
효율성  테스트
테스트 1 〉	통과 (13.07ms, 10.2MB)
테스트 2 〉	통과 (3.71ms, 10.4MB)
테스트 3 〉	통과 (8.80ms, 10.3MB)
테스트 4 〉	통과 (5.43ms, 10.2MB)

큐 없이 푸는 방식도 있는데, 이게 더 빠르다.

다 찾지 않고 중간에 끊어서 그런건가?

def solution(maps):
    answer = 0
    n = len(maps)-1
    m = len(maps[0])-1
    path = [(0,0)]
    food = [1]
    pos = 0
    try:
        while(True):
            i = path[pos][0]
            j = path[pos][1]

            if maps[i][j] == 1:
                if j<m:
                    if maps[i][j+1] == 1:
                        # 오른쪽에 길이 있다면
                        path.append((i,j+1))
                        food.append(food[pos]+1)
                if i<n:
                    if maps[i+1][j] == 1:
                        # 아래쪽에 길이 있다면
                        path.append((i+1, j))
                        food.append(food[pos]+1)
                if j != 0:
                    if maps[i][j-1] == 1:
                        # 왼쪽에 길이 있다면
                        path.append((i,j-1))
                        food.append(food[pos]+1)
                if i != 0:
                    if maps[i-1][j] == 1 and i != 0:
                        path.append((i-1,j))
                        food.append(food[pos]+1)

            pos += 1
            maps[i][j] = 0
            if i == n and j == m:
                answer = food[path.index((n,m))]
                break

    except:
        answer = -1
    return answer

테스트 1 〉	통과 (0.03ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.4MB)
테스트 3 〉	통과 (0.03ms, 10.1MB)
테스트 4 〉	통과 (0.03ms, 10.2MB)
테스트 5 〉	통과 (0.03ms, 10.4MB)
테스트 6 〉	통과 (0.04ms, 10.4MB)
테스트 7 〉	통과 (0.05ms, 10.3MB)
테스트 8 〉	통과 (0.03ms, 10.4MB)
테스트 9 〉	통과 (0.05ms, 10.3MB)
테스트 10 〉	통과 (0.06ms, 10.3MB)
테스트 11 〉	통과 (0.03ms, 10.4MB)
테스트 12 〉	통과 (0.02ms, 10.3MB)
테스트 13 〉	통과 (0.04ms, 10.3MB)
테스트 14 〉	통과 (0.02ms, 10.3MB)
테스트 15 〉	통과 (0.02ms, 10.4MB)
테스트 16 〉	통과 (0.02ms, 10.3MB)
테스트 17 〉	통과 (0.05ms, 10.2MB)
테스트 18 〉	통과 (0.01ms, 10.3MB)
테스트 19 〉	통과 (0.01ms, 10.1MB)
테스트 20 〉	통과 (0.01ms, 10.3MB)
테스트 21 〉	통과 (0.01ms, 10.1MB)
효율성  테스트
테스트 1 〉	통과 (11.73ms, 11.8MB)
테스트 2 〉	통과 (2.45ms, 10.3MB)
테스트 3 〉	통과 (6.00ms, 10.9MB)
테스트 4 〉	통과 (3.73ms, 10.6MB)

A* 알고리즘도 나온다

import heapq

def a_star(R,C,maps):
    # init
    check_list = [(1,0),(0,1),(-1,0),(0,-1)]
    path = [[100000]*C for r in range(R)]
    visited = [[0]*C for r in range(R)]
#     a star queue  guess, r, c
    queue = [(R+C-2,0,0)]

    path[0][0] = 0
    while(queue):
        guess,r,c = heapq.heappop(queue)
        visited[r][c] = 1

        for check in check_list:

            tmp_r = r+check[0]
            tmp_c = c+check[1]

            # 가생이
            if tmp_r<0 or tmp_r>=R or tmp_c <0 or tmp_c >= C:

                continue
            if visited[tmp_r][tmp_c] == 1:

                continue
            # 벽이면 넘어감
            if maps[tmp_r][tmp_c] == 0:

                continue
            if path[tmp_r][tmp_c] > path[r][c] + 1:

                path[tmp_r][tmp_c] = path[r][c]+1
                f = path[tmp_r][tmp_c] + R + C - tmp_r - tmp_c -2
                if tmp_r == R-1 and tmp_c == C-1:
                    return f+1
                heapq.heappush(queue,(f,tmp_r,tmp_c))
    return -1


def solution(maps):
    R = len(maps)
    C = len(maps[0])
    return a_star(R,C,maps)

정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.05ms, 10.2MB)
테스트 4 〉	통과 (0.04ms, 10.2MB)
테스트 5 〉	통과 (0.04ms, 10.3MB)
테스트 6 〉	통과 (0.05ms, 10.3MB)
테스트 7 〉	통과 (0.08ms, 10.3MB)
테스트 8 〉	통과 (0.05ms, 10.1MB)
테스트 9 〉	통과 (0.11ms, 10.3MB)
테스트 10 〉	통과 (0.09ms, 10.3MB)
테스트 11 〉	통과 (0.04ms, 10.3MB)
테스트 12 〉	통과 (0.05ms, 10.4MB)
테스트 13 〉	통과 (0.05ms, 10.3MB)
테스트 14 〉	통과 (0.05ms, 10.1MB)
테스트 15 〉	통과 (0.06ms, 10.3MB)
테스트 16 〉	통과 (0.02ms, 10.3MB)
테스트 17 〉	통과 (0.08ms, 10.1MB)
테스트 18 〉	통과 (0.03ms, 10.1MB)
테스트 19 〉	통과 (0.01ms, 10.3MB)
테스트 20 〉	통과 (0.01ms, 10.3MB)
테스트 21 〉	통과 (0.02ms, 10.3MB)
효율성  테스트
테스트 1 〉	통과 (17.79ms, 10.5MB)
테스트 2 〉	통과 (2.62ms, 10.3MB)
테스트 3 〉	통과 (5.78ms, 10.4MB)
테스트 4 〉	통과 (4.63ms, 10.5MB)

STACK을 사용한 풀이도 있고...

 

내 코드에서 도중에 도착하면 끊기 하니까 좀 더 빨라지긴 하지만... 여전히 느려. 왜 느릴까? 배열을 2개 사용해서 그런가?

• 중간 끊기 추가
• 거리 입력할 때 좌표 체크 안하도록
• 이미 값이 있는데 적은 값이면 체크 안하도록
• 배열은 1개만 사용하고...

이렇게 바꾸니까 속도가 1/2 정도 된다.

from queue import PriorityQueue

def solution(maps):
    #if maps[0][0] == 0: #이제 보니 이 부분 필요없네?
    #    return -1    

    pq = PriorityQueue() #그냥 큐를 써도 되는 듯... ㅡ.ㅡ;
    
    dist = 1
    sx, sy = 0, 0
    ex, ey = len(maps[0]), len(maps)
    INF = 10001 #float을 쓸 필요가 없음.
        #float("inf") #파이썬 3.5 이상에서 사용 가능
    
    for y in range(ey):
        for x in range(ex):
            if maps[y][x] != 0:
                maps[y][x] = INF
    
    pq.put([dist,(sx,sy)])
    while pq.empty() == False:
        t = pq.get()
        dist = t[0]
        x = t[1][0]
        y = t[1][1]
        
        if y == ey-1 and x == ex-1:
            return dist

        if dist < maps[y][x]:
            maps[y][x] = dist
            dist += 1
            if sx < x and dist < maps[y][x-1]:
                pq.put([dist,(x-1,y)])
            if x < ex-1 and dist < maps[y][x+1]:
                pq.put([dist,(x+1,y)])
            if sy < y and dist < maps[y-1][x]:
                pq.put([dist,(x,y-1)])
            if y < ey-1 and dist < maps[y+1][x]:
                pq.put([dist,(x,y+1)])

    return -1

정확성  테스트
테스트 1 〉	통과 (0.10ms, 10.4MB)
테스트 2 〉	통과 (0.06ms, 10.4MB)
테스트 3 〉	통과 (0.13ms, 10.5MB)
테스트 4 〉	통과 (0.09ms, 10.3MB)
테스트 5 〉	통과 (0.20ms, 10.4MB)
테스트 6 〉	통과 (0.27ms, 10.4MB)
테스트 7 〉	통과 (0.23ms, 10.3MB)
테스트 8 〉	통과 (0.13ms, 10.3MB)
테스트 9 〉	통과 (0.20ms, 10.3MB)
테스트 10 〉	통과 (0.21ms, 10.4MB)
테스트 11 〉	통과 (0.10ms, 10.4MB)
테스트 12 〉	통과 (0.08ms, 10.3MB)
테스트 13 〉	통과 (0.12ms, 10.4MB)
테스트 14 〉	통과 (0.11ms, 10.3MB)
테스트 15 〉	통과 (0.11ms, 10.4MB)
테스트 16 〉	통과 (0.06ms, 10.3MB)
테스트 17 〉	통과 (0.17ms, 10.3MB)
테스트 18 〉	통과 (0.08ms, 10.3MB)
테스트 19 〉	통과 (0.06ms, 10.1MB)
테스트 20 〉	통과 (0.03ms, 10.3MB)
테스트 21 〉	통과 (0.04ms, 10.3MB)
효율성  테스트
테스트 1 〉	통과 (84.16ms, 10.6MB)
테스트 2 〉	통과 (14.37ms, 10.5MB)
테스트 3 〉	통과 (39.36ms, 10.6MB)
테스트 4 〉	통과 (22.83ms, 10.4MB)