Programmers level2 게임 맵 최단거리

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

3번의 시도 끝에 푼 문제..

세번째 풀이

'''
모두 성공!
'''
from collections import deque

def solution(maps):
    answer = 0

    n = len(maps) - 1  # row
    m = len(maps[0]) - 1  # col
    
    def bfs(x, y):
        dx = [0, 0, -1, 1]
        dy = [1, -1, 0, 0]

        queue = deque([[x, y]])
        while (queue):
            loc = queue.popleft()
            for _x, _y in zip(dx, dy):
                nx = loc[0] + _x
                ny = loc[1] + _y
                if nx > n or ny > m or nx < 0 or ny < 0:
                    continue
                if maps[nx][ny] == 0:
                    continue
                if maps[nx][ny] == 1:
                    maps[nx][ny] = maps[loc[0]][loc[1]] + 1
                    queue.append([nx, ny])

        return maps
    
    maps = bfs(0, 0)
    if maps[-1][-1] == 1:
        return -1
    else:
        return maps[n][m]

---

첫번째 풀이

'''
- 제공되는 테스트케이스 통과
- 채점 결과
정확성: 58.6
효율성: 0.0
합계: 58.6 / 100.0
*런타임에러3개 (아마 walk_cnt_list가 비어서일듯)
'''
from collections import deque

def solution(maps):
    answer = 0
    queue = deque([([0, 0], 1)])
    n = len(maps)  # row
    m = len(maps[0])  # col
    visited = [[0]*m]*n

    if maps[n - 2][m - 1] == 0 and maps[n - 1][m - 2] == 0:
        return -1
    
    walk_cnt_list = []
    walk_hist = [[0,0]]

    while (queue):
        loc, walk = queue.popleft()
        x, y = loc
        if y - 1 >= 0:  # up
            if maps[y-1][x] == 1 and [x, y-1] not in walk_hist:
                queue.append(([x, y-1], walk + 1))
                # visited[y-1][x]=1
                walk_hist.append([x, y-1])
        if y + 1 < n:  # down
            if maps[y+1][x] == 1 and [x, y+1] not in walk_hist:
                queue.append(([x, y+1], walk + 1))
                # visited[y+1][x]=1
                walk_hist.append([x, y + 1])
        if x + 1 < m:  # right
            if maps[y][x+1] == 1 and [x+1, y] not in walk_hist:
                queue.append(([x+1, y], walk + 1))
                # visited[y][x+1]=1
                walk_hist.append([x+1, y])
        if x - 1 >= 0:  # left
            if maps[y][x-1] == 1 and [x-1, y] not in walk_hist:
                queue.append(([x-1, y], walk + 1))
                # visited[y][x-1]=1
                walk_hist.append([x-1, y])
        if x == m-1 and y == n-1:
            walk_cnt_list.append(walk)

    answer = min(walk_cnt_list)

    return answer

1번 풀이에서 틀린 부분
그냥,, 일단 정석 풀이는 아님.. (내 머리속에서 창조된것이라^^;;)
1. 막혀서 못가는 부분 처리 안됨 - walk_cnt_list의 최소값을 출력해야하는데 막힌 경우는 walk_cnt_list가 빈 리스트라 런타임에러 나는듯
2. 효율성문제: https://school.programmers.co.kr/questions/17916 이분 글 참고했을 때, 내가 짠 코드는 사람이 복제돼서 각각 움직이는 것처럼 탐색해서 그런듯

work수를 따로 줘서 끝까지 탐색하게 되기 때문에, 불필요한 탐색 연산이 많아지는듯

두번째 풀이

'''
- 제공되는 테스트케이스 통과
- 채점결과
정확성: 58.6
효율성: 30.1
합계: 88.7 / 100.0
* 3개 실패
'''
from collections import deque

## bfs(): 이동 후 방문한 위치 값 최단거리로 변경하기
def solution(maps):
    answer = 0

    n = len(maps) - 1  # row
    m = len(maps[0]) - 1  # col
    
    if maps[n-1][m] + maps[n][m-1] == 0:
        return -1
    
    def bfs(x, y):
        dx = [0, 0, -1, 1]
        dy = [1, -1, 0, 0]

        queue = deque([[x, y]])
        while (queue):
            loc = queue.popleft()
            for _x, _y in zip(dx, dy):
                nx = loc[0] + _x
                ny = loc[1] + _y
                if nx > n or ny > m or nx < 0 or ny < 0:
                    continue
                elif maps[nx][ny] == 0:
                    continue
                elif maps[nx][ny] == 1:
                    maps[nx][ny] = maps[loc[0]][loc[1]] + maps[nx][ny]
                    queue.append([nx, ny])

        return maps[n][m]
    
    return bfs(0, 0)

2번 풀이에서 틀린 부분
적팀의 위쪽과 왼쪽이 막혀있는 경우만 못가는 경우가 아님
막혀있어서 못가는 부분을 변경해주니 실행됨!