Py) 프로그래머스 1844 게임 맵 최단거리

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

카페 영업시간 다 돼서 쫓겨나는 중이라 내일 이어서))

0. 입출력

 

1. 김예고리즘

1-1. 알고리즘

1) 최단 경로를 검색한다고 하기에 bfs라고 생각함
2) 1을 만나게 되면 큐에 넣어줌
3) 끝까지 간 다음에 결과를 저장하고, 큐에 들어있는 경로로 그 시점부터 다시 탐색, 결과 저장을 반복

1-2. 코드

from collections import deque
def solution(maps):
    answer = 0
    deq = deque()
    # 우, 좌, 상, 하
    deci = [(0,1), (0, -1), (-1,0), (-1, 0)]

    row = len(maps)
    col = len(maps[0])
    goal = (row, col)
    now = [0,0] # 현재 좌표
    step = 0

    if maps[row-1][col-2] == 0 and maps[row-2][col-1] == 0:
        return -1

    while now == goal:
        for i in range(len(deci)):  # 4번 반복
            # 범위를 벗어난 경우
            if maps[now[0] + deci[i][0]] >= col or maps[now[1] + deci[i][1] >= row]:
                continue
            if maps[now[0] + deci[i][0]] < 0 or maps[now[1] + deci[i][1]] > 0:
                continue

            # 현재 좌표에서 계산
            if maps[now[0]+deci[i][0]][now[0]+deci[i][1]] == 1:
                deq.append((now[0]+deci[i][0], [now[0]+deci[i][1]]))

        # 현재 위치를 큐 맨앞 원소로 변경
        change = deq.popleft()
        now = change
        step += 1

    answer = step

    return answer

print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]))

 처럼 하다가 예전에 비슷한 문제 푼거 참고해서 다시 다 갈아엎고

from collections import deque
def solution(maps):
    answer = 0
    deq = deque()       # 좌표, 현재 비용, 방향
    #     좌 우 상 하
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

    N = len(maps)
    M = len(maps[0])

    now = [0, 0]  # 현재 좌표
    step = 0

    if maps[N-1][M-2] == 0 and maps[N-2][M-1] == 0:
        return -1

    deq.append((0,0,0,0))  # 좌
    deq.append((0,0,1,2))  # 상

    costview = []
    while deq:
        x, y, cost, direc = deq.popleft()
        for k in range(4):
            x += dx[k]
            y += dy[k]
            if 0 <= x < N and 0 <= y < M:
                if maps[x][y] == 1:
                    cost += 1
                    deq.append((x, y, cost, k))
            if x == N and y == M:
                costview.append(cost)

    answer = min(costview)



    return answer

너무 오랜만에 해서 그런지 머리가 안돌아가길래 그냥 찾아봄

방향 때문에 헷갈리는 것도 큰데 bfs 진짜 으으으므으름ㅁ을믕ㄹ므

 

2. Solution

2-1. 사용 알고리즘: BFS

2-2. 사용 자료구조: 큐

2-3. 로직

deq에 append 된 한 위치에 대해 4가지 방향을 바꿔가며 길인지 벽인지 확인
길인 경우, 맵의 해당 위치에 비용을 적어줌

2-4. 코드

// 12, 15, 16 틀림

from collections import deque
def solution(maps):
    answer = 0
    N = len(maps)
    M = len(maps[0])
    visited = [[False]*M for j in range(N)]

    que = deque()
    # row+1, col+1, row-1, col-1
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    que.append((0, 0))      # 현재 위치
    visited[0][0] = True

    if maps[N-2][M-1] == 0 and maps[N-1][M-2] == 0:
        return -1

    while que:
        cx, cy = que.popleft()
        for k in range(4):
            x = cx + dx[k]
            y = cy + dy[k]

            if 0 <= x < N and 0 <= y < M:
                if maps[x][y] == 1 and visited[x][y] == False:
                    maps[x][y] = maps[cx][cy] + 1
                    que.append((x, y))
                    visited[x][y] = True

    answer = maps[N-1][M-1]
    return answer

 

정말 억울한게, 원래 소스와 큰 다른 점이 보이지 않는데 원래 솔루션 소스는 통과되고 내 소스는 12, 15, 16에서 틀렸습니다가 뜸..
내가 피곤해서 차이가 안보이는건가..

 

// 정답

from collections import deque

def bfs(arr, x, y) :
    q = deque()
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    q.append((x, y))

    while q :
        cx, cy = q.popleft()
        for i in range(4) :
            nx = cx + dx[i]
            ny = cy + dy[i]
            if not (0 <= nx < len(arr) and 0 <= ny < len(arr[0])) :
                continue
            if arr[nx][ny] == 0 :
                continue
            if arr[nx][ny] == 1 :
                arr[nx][ny] = arr[cx][cy] + 1
                q.append((nx, ny))

    return arr

def solution(maps) :
    bfs(maps, 0, 0)
    if maps[len(maps)-1][len(maps[0])-1] == 1 :
        return -1
    else :
        return maps[len(maps)-1][len(maps[0])-1]